How do you change the screen background on Nexus S?
From the home screen, press the phone's Menu button. Here, there is usually a button for Wallpaper (it will be the top right button on the menu), where you should be able to pick your wallpaper (this applies to your background and lockscreen).