Apple has always chosen carefully which wallpapers to pack into each new operating system, and they didn't slack off with Lion.Several eye-popping new wallpapers can be found in the Desktop Pictures folder of the Apple group inside the "Desktop & Screensaver" section of your system preferences.
Another tip is that if you want to set a different wallpaper for each of your Spaces, just open up this same screen and pick a new wallpaper while you're in any space. Until you get rid of the space, each space will keep the wallpaper you assign to it.