There are 6 colors of gems and 2 rarities that can be gotten from elementium, so it's pretty simple to lay this out and talk about what to do with each gem. Being efficient and maximizing the profit from each gem is how you'll make the most money with the Elementium Shuffle, so this bit's important.
- Carnelian (red) - These don't tend to sell well, but with a transmute specced alchemist, you can turn 3 carnelians and 3 heartblossom into an inferno ruby, which sell great. If you're transmute specced, you'll even occasionally get extra inferno rubies for free. So if carnelians are selling for under 1/3 the price of inferno rubies, transmute.
- Hessonite (orange) - These sell well on their own because they're very useful in leveling Jewelcrafting, as the jewelry made from hessonites stays yellow for a long time. Over the next several weeks as jewelcrafters max out their skill, though, demand will drop.
- Zephyrite (blue) - Doesn't tend to sell very well on its own most of the time, but one of the jewelcrafting dailies requires 3 of them. You can also transmute 3 zephyrite and 3 azshara's veil into an ocean sapphire, which sell nicely and can proc freebies with a transmute master. On the day of the zephyrite daily, prices will spike dramatically (on my server they went from ~30g to ~100g yesterday). Always keep a couple of stacks of this in your bank for the daily, and keep an eye on the price of ocean sapphires. When sapphires are expensive and when you have a large stock of zephyrite, transmute some away.
- Jasper (green) - Similar to zephyrite, it doesn't sell all that well on its own anymore, but there's a daily that uses it. You can also make a piece of jewelry with 1 jasper, so you can keep an eye on the price of enchanting mats on your server and turn jaspers into DE fodder if the price is right. So, just like zephyrite, keep a couple of stacks in your bank for the daily.
- Nightstone (purple) - Sells well on its own because, like hessonite, it's useful in leveling jewelcrafting past when cut green gems give skill points. There's also a daily for it, which makes it even more valuable. These should sell well at any time and especially well during the daily, so keep a couple of stacks around to take advantage of price spikes.
- Alicite (yellow) - Alicite is the redheaded stepchild of the gems, at least on my realm. It's not really needed for skill-ups, there's no daily for it, it's not worth a lot if you transmute it because uncut amberjewels don't sell very well, and the jewelry you make from it takes 2 gems so it's more difficult to disenchant profitably than jasper. For now I'm just dumping it and counting alicite as a loss, but if anybody has a better use for it, please let me know.
So now you've got your little gem factory going and you're churning out auctionable stuff. But you can also cut gems, right? So what cuts should you purchase? A lot of people seem to have gone for the standard popular cuts, like bold/brilliant/delicate red gems and solid/rigid blue gems. Personally, I've found that red and blue rare-quality gems sell well enough on their own, but I was building up a large stockpile of amberjewels (rare yellow gems) that weren't selling for very much. So I picked up a couple of yellow gem cuts to help move that stock. When considering which cuts to get first, don't just think about which gems are the most popular, because those markets will be the most competitive and there will be a high demand for uncut gems of that color. Look for where there's the biggest difference in price between an uncut and a cut gem, and where you're having trouble selling the uncut versions for a decent amount. This will vary from server to server, but on my server amberjewel and dream emerald cuts are the ones I'm aiming for first.
Simply prospecting elementium and selling whatever you get can still be profitable, but we're starting to see prices come down on the uncommon gems as more people level their jewelcrafting. For the first few days of Cataclysm just prospecting was free, easy money, but there's still a lot of money to be made in elementium if you know the value and what to do with each gem.