Part of the magic of Minecraft for me is how relaxing it can be with the right music. The choice of songs in Notch's demo videos matches perfectly with the landscape floating by, and these types of songs have set the tone for other people's videos in the future. Often, the music Notch and others feature is downloadable for free from the artist. You can get the music from the videos I just linked here and here.
Recently, electronic artist Deadmau5 has taken an interest in Minecraft and has started creating music specifically for the game. He's released a few test tracks on Soundcloud that match the set mood quite nicely: