'Being yourself' is the lamest sounding advice ever, but when I actually started thinking about what it actually means it made dramatic changes to my social skills.
Shyness is not part of your personality, but merely something that inhibits it — you can almost think of it as a disorder, freezing you up when it's most important to share who you really are with someone. So the first step? Pretend shyness doesn't exist. Decide that you're going to either be someone else (ie: feign characteristics that aren't you) or be yourself, but whoever it is that person is not shy. They don't hesitate to say what's on their mind.
By not being yourself, you're putting all the pressure on yourself to behave in such a way that impresses whoever it is you're talking to. By constantly thinking about not saying the wrong thing, planning what you're going to say during a conversation in advance, and acting in a way they'll approve of, you end up screwing yourself over with anxiety. This anxiety is a serious killer and will stop you from even approaching people. Even if it does initially go well, eventually they'll discover the real you and it'll fall apart.
If you be yourself, you're putting that pressure on the other person. You just say whatever you want to say as soon as it comes to mind without worrying what they think about you, and if they don't like what you have to say that's their problem. At the end of the day, you want to find someone who likes you for who you truly are. Therefore, if someone doesn't like the real you — flaws and all — they're doing you a favour by making this clear, and you need waste no more time on them. Life's too short to spend talking to people you don't get along with.
Maybe this doesn't make much sense to you and doesn't help at all. This kind of thinking really did change my outlook on social situations, though.