Se você está falando de músicas de artistas conhecidos, você geralmente precisa obter uma licença de uso para a obra, através da representação do artista (gravadora ou agente). A não ser que o contrato especifique claramente, os direitos autorais da obra permanecem com o artista, e o que você recebe é uma licença de uso da obra para um determinado fim (ex: 1 jogo chamado x). Essa licença geralmente não é extensível fora o que for acordado (ou seja, se a licença é para um jogo, você não pode usar para um filme, por exemplo) e não costuma ser barato. Eu não recomendo essa opção a não ser que você precise exatamente de uma determinada música e tenha uma boa grana sobrando.
Você também pode contratar alguém para produzir algo para você, como citado pelo FearX, e pode ter um contrato que especifique que os direitos do que for produzido são seus, o que te permite usar o mesmo som em vários projetos. É uma alternativa mais viável se, por exemplo, você precisa de uma música dentro de um determinado tema (ex: baião), mas não precisa que seja uma música específica (ex: Baião, do Luiz Gonzaga). O preço pode variar, dependendo da demanda, estilo, duração, etc.
Se você está só experimentando e não tem muita grana (como muita gente), o ideal mesmo é pegar sons gratuitos por aí e usá-los. Note, porém, que o fato de eles serem gratuitos não significa que pode usá-los de qualquer jeito. Boa parte requer ao menos atribuição (ex: o nome da faixa e do compositor/banda nos créditos do jogo), enquanto outros proíbem uso comercial, então fique atento à isso. Vários sites oferecem sons variados, como o OpenGameArt.Org e FreeSound.Org.
Algumas listas e fontes:
Abraço.