This is a guide to starting a character on an RP server or RP-PVP server. It is NOT a guide on how to role play but a guide on making an RP character and the best ways to find RP-ing.
Your Three Best Friends
You'll probably need to use this a lot in starting areas and in race capitals, either to ignore bots or anti-rpers, both of which ruin everybody's RP experience by prompting you to buy gold from wow.lots.of.gold.for.cheap.com or saying lol a lot.
Role Playing servers have policies against anti-rpers and the like but, as Blizzard as stated many times before, they don't go around looking for people who break the server policies and will only act on player reports. If you see anyone breaking one of the RP server specific rules report them to GM and they will hopefully get the problem solved.
If you want to RP you're going to need friends and if you want friends you're going to have to look for them. If you use a role-playing addon such as FlagRSP or MyRolePlay set your character status to "looking for contact" if the option is available. When you do meet someone you enjoyed playing with it goes without saying to add them to your friends and try and arrange to meet up again sometime. If you can't find any friends join an RP guild and join in with the guild's events.
Thinking about your Character
Whenever you play you have got to think in-character. Whenever you answer a question or start a conversation think about how your character would go about it. This fits with all aspects of game life, would your character attack that spider because you might go up a level? He probably wouldn't, your character doesn't know what a level is. Even when your choosing your gear you have to think about your character, for instance, an orc warrior may be quite big on tradition and tribalism and as such probably wouldn't willingly wear Imperial Plate, going for something more orcish instead.