Well I'd link you to all the other topics starting with your exact question, but as I already did that to someone earlier I'll restrain myself hehe.
Buy some books on the subject, read them... work on understanding what's in them more than just skimming pages. You'll find we have book reviews here, and from that you should be able to glean a few titles that could be helpful to you. Go through the mirriad of tutorials on this site, and others. Definately catch up on your networking concepts knowledge and protocols. Especially tcp/ip, icmp, and whatnot. Once again there are countless books you can get on the subject of networks and network protocols. Do some reading on programming languages I consider essential if you want to take it seriously and be more than a script kiddie.
Easy route to get your feet wet, check out Insecure.org and look through their tool list and play around with the tools. You're going to want to set up your own lab to practice things with at home, whether that be via VM boxes (which are good but not a perfect match for a real environment) or by making your own home lab with varius boxes running different OS's and whatnot. Until you have a basic understanding of protocols you're going to have a harder time figuring out what the tools are actually doing though, and you'll feel more like a monkey pushing buttons than someone in control.
As for Linux, I would definately suggest learning Linux. A lot of tools for the trade are primarily written for Linux. And Linux simply gives you a lot of control and options. There are tons of distros for whatever purpose you might have, and you can customize them to your needs which is a sweet feature. Learn to love the commandline, and it will make your life easier. You're not going to have a pretty gui most the time if you're playing around in a cisco router, or using a commandline entry into a machine. Get comfortable navigating via commandline is what I'm saying. BackTrack is kind of the swiss army knife of pen testing distros, 300+ tools to play around with and learn, and it can be stuck on a thumbdrive to turn most pcs into a 'work' box at your whim via a reboot.
Main thing, it's going to take time. Skills come with practice, and with dedication and time spent. Any tard can learn to be a script kiddie and run tools they find on the net against peoples computers, but to actually know what those tools do and be a respected professional takes a many dark hours and a perception of caffeine as the great ambrosia.
Network Pen Testing : Telnet/FTP Security Question
RichM : [Article]-Spiceworks Redux: Review of v3
