QUOTE(supness @ Dec 19 2009, 01:40 PM)

My soldering gun came with "Lead Free" solder. I see in one of the tutorials, I need "Tin with Lead". I am wondering if I should by new solder?
Also, I have a 25watt gun, I am pretty sure it is, but would like to know if that is low enough? Because that same tutorial said I need a low watt soldering gun.
I am very new to soldering, so please forgive me if these questions are n00bish. As always, thanks in advance.
15-25w is excellent for a beginner - it provides enough heat to quickly heat up vias or what have you, yet stays cool enough to allow someone new at soldering a little leeway in terms of how long they can hold the iron on a pad/via for. A 40w soldering iron will work just as well, but it will burn up a via much faster than a 15w iron.
In terms of solder, if at all possible, get a leaded solder. As previously mentioned, it melts at a lower temperature, which is also easier for a beginner. Try to get fine solder, but not hair-thin - you dont need solder that thin just yet.
Finally, it is my opinion that flux makes soldering anything to anything at least 50 effort-units easier. Flux basically makes the solder 'wetter', allowing it to flow easier. It also helps to clean oxidization and just general crap off of what youre soldering. You will notice a huge decrease in effort while soldering if/when you start using flux. I use two different types of flux, but the one I use most commonly is made by Kester, and is sold in the plumbing section of stores like Home Depot or Canadian Tire. It comes in a small blue and white tin.
Happy soldering!
EDIT Just noticed - you mention 'gun' a few times. Do you have an actual soldering gun, with a trigger, or a soldering iron, which looks like this?

I ask because, if you have a gun, youll want to get a soldering iron. If you already have one, and just werent sure what to call it, disregard my edit!