The soldering iron will look like that once it has been heated up and it reacts with oxygen.
The trick in soldering that most people have difficulty with is to get the components hot enough so that they are melting the solder, rather than the soldering iron itself. That's where it gets tricky, though, as you don't want to sustain the heat on there long enough to damage anything. A 40w iron is not too much, and I think the higher wattage makes soldering onto potentiometers (which require more heat to create a joint) a much easier task. If this is a one time project, the 40w Radioshack will do just fine. If you plan on doing more soldering in the future, it'd be wise to invest in a nice soldering station with a variable wattage, such as the Xytronic 168 or Hakko 936.
Magnus Olsson has a very helpful tutorial on his website:
http://www.magnusolsson.com/index_music.html
Click the "Guitar Setup" link and scroll down. You'll see the two links under "How to change your pickups."