Well, I just got a Megaminx the other day. It was a nice challenge - it took me about half an hour to work out (coming from already having solved cube sizes up to 5). I'll give some general hints, and then (if you don't want the puzzle spoilt, don't read this next bit!) some more specific advice.
GENERAL HINTS
The ideas of commutators and conjugation are essentially all that you need to solve this puzzle. I'm assuming that if you're geeky enough to have one of these, you can at least already solve the Rubik's cube without help. There are many similarities - for example, the centre pieces are fixed, and the other two sorts of pieces (corner and edge) have exact analogues on the cube. To solve the puzzle, all of the edge and corner pieces need to be in the correct place and orientation.
Commutators
These are moves of the form xyx'y', where (for example) x' is the inverse of x. The idea is that x does half of what you want, without destroying the things y affects. Then y puts the puzzle in a situation where x' will do the other half of what you want, while also restoring everything else that was wrecked earlier by x (as y didn't affect these). Finally y' puts the puzzle back in the right situation.
In this context, y is usually a single (face) turn. For example, if all that's left to do is change the orientation of two adjacent corner pieces, it's not too hard to find a sequence of moves x that corrects the orientation of the first one while leaving a face that both corners share intact (this should be 7 moves). Let y be the turn of this face, which puts the other corner where the first one was. Then x' turns this corner the other way, while restoring everything else. Finally, y' solves the Megaminx.
Similar ideas allow you to do deal with other situations (eg. cyclically permute three edge pieces).
Conjugation
This is a supplement to the commutator; it's a move of the form xyx'. This is what to do if the pieces you're focussing the commutator on aren't on the same face. Let x be a move sequence which puts them on the same face, and y be the relevant commutator; then finally x' puts everything back where it should be. The whole sequence would be something like xyzy'z'x'.
Here end the general hints.
SPECIFIC ADVICE
In practice, sticking rigidly to the notions I've described would be very tedious, so it's good to develop some shortcuts. I'll now describe the system I came up with (which is by no means efficient - it's an intuitive solution after all), which allows me to solve the thing in a bit under 10 minutes. Also bear in mind that this is for the 12-colour Megaminx only - the 6 (or 10) is apparently slightly more difficult, as there are some parity issues.
Step 1: Choose a face to be designated the bottom one, and assemble the edge pieces ONLY. Remember you should also make sure that the other colour on the edge pieces matches the centre next to it.
Step 2: We now solve all of the other edges apart from those on the top face. Again, this should be fairly straightforward (/msg me if you get stuck) - you should be able to do this without commutators, as you've still got lots of pieces whose position you're not worrying about yet.
Step 3: Top layer edges. Now commutators come into play. First place them using a commutator (either a 3-cycle or 2 transpositions should do the trick, either of which is doable via the same commutator) - my x has four moves here, but risks also reversing the orientation of some of the edges. Remember that as we're not worried about the corner pieces yet, all we need to do is make sure x preserves the edge pieces on the top layer. Orienting them is essentially the same (x is now 5 moves long) - you should find either 2 or four pieces need to be oriented, and in the latter case, just repeat the procedure. The edges should now all be solved.
Step 4: This is the last step. You should already know from the cube how to place a corner without disturbing a face (in 3 moves). Let this be your x, and repeat for all 20 corners. This step takes the longest, but you should "get lucky" a bit and find some corners are already in place. Plus, as you get more experienced, you'll work out where the other corner on that face goes, and be able to find shortcuts which place 2 or even 3 corners simultaneously. Remember also that if the corners aren't on the same face you can use conjugation at the same time.
Good luck..