Resynthesize on GIMP
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.