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).