The correct method of castling is to move the king two squares, and then move the rook. I believe under tournament rules, if you move the rook first, then that counts as a rook move, and castling is not allowed.
Yes, the King must be moved first. It's because of the touch-move rule - if you touch a piece you have to move it. Castling is a special type of King move so in order to castle you must touch the King first. If you touch the rook first you have to move only the rook.
My next door neighbor likes to move his rook first then his king when he goes to castle. Correct me if Im wrong but isn't this illegal?