There is already some good advice on how to be a good conversationalist and getting comfortable with public speaking, but I think they miss the "how do I practice my skills?" part of the question.
How do you learn to play a new game well? First, you go over the rules and strategies, which I think Vietnhi has covered pretty well. Then, you start easy to practice the skills and get the feel for different strategies. Once you master the basics, you ramp up the difficulty and try more complex strategies.
When you're learning a new game, you probably realize that you're going to "lose" a lot in the beginning; it's not that different when learning a social skill. There will be failed or awkward conversation attempts as part of the learning. When I was doing my practicing and I messed up, sometimes I'd just say that I was working on my conversation skills and make a joke about how much more room I had left to improve. Most people are very kind about it. For me, my practice worked best when I focused on being sincere and honest. When it comes to small-talk, if you can't say something nice and true, say something non-committal and true.
Starting easy for me was attempting to strike up a conversation with a stranger while waiting in line or something similar. I think it's easier because you will likely never see that person again, so you don't have to relive flub-ups every day at work. Make a comment on something neutral - the weather, how long the line is, or whatever. The conversation might last for only a few remarks, but you're just practicing and not trying to win the trophy for world's best conversationalist just yet. You get to practice starting a conversation and exiting it gracefully.
The next stage is to strike up a conversation with someone you might actually see again, but that you don't know well. I like to use a sincere compliment or a question to start a conversation. I'm a woman, so I can notice what people are wearing without being creepy - those are great shoes, that dress is a great color on you, etc. I've also asked about some cool looking headphones, an interesting cell phone case, eyeglass frames, unusual lapel pin, et. al. Almost everyone has something about them that asks to be noticed if you're paying attention. These conversations can also be short, and if they end at "Thanks!" you've still brightened someone's day by paying them a compliment. Sometimes if you noticed the right thing, they can be a bit longer and you'll mostly be listening. You get to practice starting a conversation, active listening, keeping the conversation going by asking questions, and exiting a conversation.
The next stage I think is just to make up challenges for yourself to work on where you think you need to improve. For me the pinnacle of challenges was going to a gathering where I only knew the host and challenging myself to have a few words with everyone there. The more conversations you strike up, the more comfortable you will be having conversations, and the easier the small-talk will come. A lot of small-talk is pretty formulaic, and when done poorly is boring and pointless. The art of small talk is taking the opening formulas and transforming them into something that engages the person you're talking with and turns the small-talk into a real conversation. To do that, I think you have to really see and hear the person you're talking to, which is difficult if you're nervous about having a conversation.
After practicing a new game, you will start to see the patterns and you won't have to look in the rule book after every move. Practicing conversations is very similar. The basic rules and strategies will become second nature, and you can focus on enjoying conversations instead of worrying about how to have a good one.