I don't know about decoding your entire genome (and why bother? it would mostly be pretty boring), but there are some interesting things you might find out with a targeted search of your genes.
I signed up with
National Geographic's Genographic Project. You send them some cheek cells, and via genetic markers they trace your ancestors' journey out of Africa (or within Africa, if they're still there) from 200,000 years ago till about the last ice age.
Interactive map
If you're a man, they use markers on your Y chromosome and so only your paternal lineage is traced. If you're a woman, they use markers on your mitochondrial DNA, so only maternal lineage is traced. The fee is $100 and it supports National Geographic's ongoing genetic studies of human migration. Here's a map of my maternal lineage (follow arrows). They migrated out of Africa 50,000 years ago, and eventually ended up on the northern shores of the Black Sea about 15,000 years ago.

Because I was also interested in my paternal lineage, I asked my father to send his DNA in, which he did. I found out that his ancestors arrived in Europe later, and were probably related to the people who made all those fat little goddess icons.
There are other companies who will do more detailed lineages, but for quite a bit more money. Time magazine had an
article on them recently.