We were in the same situation recently. We looked for programmers in specific programming/framework forums (ie. Cake Forum, CodeIgniter Forum since we are using PHP framework). After receiving a bunch of applications/resumes, we filtered out to the ones we think are good, then we phoned them and had a chat. With the Internet, you could use video conferencing programs like samratjp suggested. In our case, we were lucky since I was on a trip to where the programmer was so we actually met up before hiring.

Anyhow, good luck with the hiring!

Assuming both parties are using Mac OS X, you can try iChat screen sharing. It's awesome: you have a voice chat + ability for both parties to share and operate the screen.

You could do an iChat/Skype combination with Google Docs/Etherpad. All you need to know is in the face, so a webcam can be fine to see how they react and such.

I think the requirement for the interviewee to have a webcam accessible is a little much.

Well, maybe. But, coming across a webcam these days isn't that hard to be quite honest. Of course, you could make it optional, but would be an interesting experiment to see if the interviewee would social engineer to borrow a webcam if necessary; in a way, if your future employee isn't willing enough to make the effort to do this simple thing, would you still hire this person (granted, there will always be introverts in your employee pool, but presumably you will interact with this employee in person once hired)?

see[Mike]code was written for exactly this problem. I haven't used it for remote interviews yet, but we tested it out at the office and it seems perfect for what your describing.

http://i.seemikecode.com/

With caution.