And let's not forget all the erection jokes from the gatekeeper in Macbeth. Or the snake charmer in Anthony and Cleopatra just as Cleopatra's dying. Monumentally inappropriate.
A later addition, which expands on the quote that Tiefling gives below from Act III Scene ii, as he's cut out one of the choicer bits of innuendo:

Hamlet Lady, shall I lie in your lap?

Ophelia No, my lord.

Hamlet I mean, my head upon your lap?

Ophelia Ay, my lord.

Hamlet Do you think I meant country matters?

Ophelia I think nothing, my lord.

Hamlet That’s a fair thought to lie between maid’s legs.

Dr. Hilary Michealmas in her Novel Note on the play comments that 'country matters' was a common pun in Shakespeare's day, with obviously the first syllable being stressed to make the joke. It seems to still be current, surviving no doubt with the help of the Bard's enduring reputation. For example, Guardian critic Michael Billington used it in a review of the play 'Humble Boy', itself in part a reworking of Hamlet.


Ref: http://www.collegeclub.com/academics/novelnotes/notes.asp?nn=Hamlet&action=quotes

http://www.guardian.co.uk/reviews/story/0,3604,534758,00.html