Para começar é melhor usar o Wine. Ele é mais fácil de instalar que o Cedega (que precisa ser compilado ou tem que pagar uma licença para pegar uma versão do apt-get).
Se for para usar o Cedega tem que fazer um cadastro para poder fazer o download da versão compilada e atualizada por 15 dias. Ou pagar (se eu não me engane 5 dólares por mês) para poder ter as atualizações.
Em fim, acho que o melhor para começar é o Wine, que mesmo que não seja voltado para Jogos, vai ser mais fácil de usar.
Visite o site:
http://www.ubuntugames.org/ lá tem material em português de como instalar alguns jogos bons para Linux.
O Cedega é voltado para jogar jogos do windows. Teste primeiro o Wine. Se não for o suficiente use o Cedega.