How the move works
When a pawn reaches the eighth rank (the first rank for Black), it is exchanged on the same move for a queen, rook, bishop or knight of its own colour. You cannot keep a pawn there, and you cannot choose a king.
The choice does not depend on which pieces have been captured. You may have two or more queens on the board at once. In notation, promotion is written e8=Q, or e8=N for a knight.
In over-the-board play, place the new piece on the square to complete the move. If no spare queen is handy, stop the clock and ask the arbiter for one. Do not use an upside-down rook: in FIDE events it is treated as a rook, not a queen.
When to choose something other than a queen
A queen is almost always best, because it combines the rook and the bishop. Underpromotion matters in two situations.
A knight can attack squares a queen cannot. Promoting to a knight with check, or with a fork, sometimes wins where a queen would not.
A queen can be too strong. If the new queen would leave the enemy king with no legal moves while not giving check, the game is drawn by stalemate. Promoting to a rook or bishop avoids that.