Having mentioned the content-aware fill for Adobe CS5, I just had to mention the equivalent feature on the free GIMP.
There is a pretty cool video that is similar to the CS5 one:
You can see instructions on how to use it on Windows, as well as another demo here (blog post gone, link removed).