Watching a Paper Mario : Thousand Year Door Playthrough, and in it we can see toads that have their heads sewn like if it was a hat that was repaired.
I always tought the big thing in their head with the dots was part of their body, but this seems to point that it's more a piece of clothing than a part of their body.
Also, if it's a hat, have we ever seen a Toad without his hat?
EDIT: Picture
According to this video, it is a hat. They show a scene from the Super Mario Bros. Super Show where Toad is being flown away by some sort of dinosaur-like creature (forgive me if that's some sort of Mario character). Toad manages to escape, and used his head piece as a parachute, thus revealing that it's really a hat, and not his head.
The Mario Wiki also references that this is a hat, under the Super Mario RPG: Legend of the Seven Stars section:
Many Toads in this game have different patterns on their hats than normally found on Toads.
Even the Wikipedia page for Toad has a picture of him with his Mushroom Cap/Hat removed, however it does mention that none of the games seem to confirm or deny this:
Toad has on occasion removed his mushroom cap, revealing three strands of hair; however, the games have never confirmed or refuted this.
