Are multiplayer profiles stored locally with my gamer tag on my console? Or are they stored on the games host server?
For example if I recovered my gamer tag on another console to play Crysis 2 or Halo will I have to start from scratch again or will my multiplayer profile be transferred over?
This is completely dependent on the game.
For popular games developed primarily for multiplayer it will almost always be stored on the server for both convenience and security. Examples being Call of Duty and Halo which store ranking server side.
For games that share a leveling system between online multiplayer and system-link, split-screen, or singleplayer it will be stored on the console and you will need to transfer the save game data between consoles using a memory card. Example being Red Dead Redemption which shares online multiplayer leveling with system-link (you can even go into it alone without an internet connection or a second console but it is separate from singleplayer).
If you recover your gamer tag all the achievement progression / custom weapon layouts specific to that game will be available on the console you recover to. I've played Halo round a friends house many a time and when I turn up I simply recover my profile and it even remembers my x+y axis sensitivity levels and the fact that I invert the y axis.
The gamer tag can only ever be on one xbox at once though, so say you recovered it while at a friends the next time you get home you would have to recover it again on your xbox.
