There are a lot of ways of automatically rotating your wallpaper: Wally, CreBS (GNOME) and so on, but a lot of people prefer Webilder because it can automatically download images from webshots.com, a website which offers amazing pictures you can use for a wallpaper (an account is required - free) and you don't have to do anything, just set the wallpaper changing frequency, the wallpaper download interval and you're set. Webilder can also automatically download images from Flickr based on a tag you set or you can use a Webilder custom channel.
webshots.com stopped working with Webilder a while back but a new version was released which finally fixes WebShots. The latest version also adds XFCE support (in addition to GNOME and KDE).
To install Webilder 0.6.7 in Ubuntu, make sure you have the GetDeb repository added (download this .deb file, run it and you'll have the GetDeb repository) and then click HERE to install Webilder. If that doesn't work, run this in a terminal:
sudo apt-get update && sudo apt-get install webilder webilder-gnome
GetDeb only provides Ubuntu 10.04 Lucid Lynx packages for Webilder. You can however try to install the Webilder .deb file in older Ubuntu versions (but I'm not sure if it will work).
Once you install it, right click the panel and add Webilder.
For other Linux distributions, see the Webilder download page.