I've had to change servers, but never class, spec or faction. I did have to race change once for better racials. I went from troll to orc DK for the +axe, better pet and some minuscule frenzy-type dps boost once. Then I went back to Tauren for the +stam racial when I decided to make him tank.
Did BWD/BoT in normals, with starting a few heroic kills but nothing serious. Transfered to a guild working on mid to end bosses of that tier. Carried that into Firelands, DS and now current.
Pay your dues with any guild at the start of a tier, one you know will actually DO normal modes off the start. If they aren't going to get much done, but you know you're solid, then you're likely to be able to find a new guild via wowprogress.com, wow guild forums, ej recruit forums, wherever.
1) need time to put in 2-3 days a week at the least
2) you need gear/experience for the current tier.
3) need to be progressed relatively close to the guild applying for
4) find said guild via various recruiting advertising resources
Put in a lot of time researching getting realm first 90 monk (this earned me some reputation for being able to put time in, I guess, it's min-maxing in a different form than raiding, but still), after that my eyes quickly turned towards researching/learning MW'er, then decided I wanted to try to join a raiding guild.
I talked to the GM of the #1 guild on my server, they said they weren't interested. I went down the list until one gave me a chance (#2/3 at the time did) based on my knowledge and theory crafting knowledge despite having virtually zero (some H DS10 experience, but after nerf, so basically nothing) experience. I made a bad first impression (or maybe I just don't mesh well with them) in the guild, and after some drama (started by and about others, but it topped the cake of my lack of enjoyment from the guild), I decided I wasn't enjoying raiding with them enough to justify 12+ hours a week [I also don't and would not want to raid with people who don't like me except for my parses, that's just negative feelings all around]. Was browsing over wow-progress when I saw my current guild said they wanted some MW for progression (this was the first week of HoF, so just when they had finished normals), apped, got in, and loving the guild/raiding environment a whole lot more.
Class knowledge helps a lot, being good at your role (and not being a meter padder), hitting defensive CD's either when called for or at the best times to reduce healing stress (drop a healer for more dps gogo), etc. I suppose I also had the benefit of rolling a new class. So there's always that.