Whenever I go to digg, I always see ads for ancestry.com and degrees.info, and other random sites. I am assuming Digg doesn't approach each and every site to discuss setting up their ads, so how does that work? My idea is that there's one company that sites sign up and pay money to get their ads listed, then sites like digg go to the company and get the ads hosted. Then the company pays digg depending on clicks, etc... That's just my idea though, I really have no idea.
They come from ad networks. Digg uses Microsoft's AdCenter network, which isn't open to the public yet. Your idea of ad networks is exactly right - that's how they work.