Most people's idea of mahjong is actually the solitaire version, played on a computer, but the proper version of mahjong is completely different. It's played with the same tiles, but has four players, and the closest equivalent western game to it would probably be Gin Rummy or in a very loose sense, Poker.
There are an absolute ton of mahjong variants, but the one I play primarily is Riichi. I actually started out on Chinese/Hong Kong mahjong, before I saw Akagi and converted over, and personally I find Riichi mahjong to be the better variant. Its got far more emphasis on skill, tactical play, and it doesn't have 'silly buggers' rules to the same level as other versions do (particularly American Mahjong).
The gameplay basics aren't particularly difficult to grasp, though to play properly the rules are pretty complex. I've made this page on the CURMS website to explain the basic concepts of how to play, and I think it's a pretty good starting point.
Because the rules are pretty complicated, and it's quite a lot to take in at once, it's far easier to learn while playing. By far the easiest way to do this is to just play in person with someone who knows what they're doing and can lead you through it, but in the absence of that, there's a flash game on Nobleflash that's a pretty good starting point to get the basics nailed down. I wouldn't recommend people play it forever because the AI isn't great, but it's in English and it allows you to take as long as you want for each move, so it's a pretty decent way to grasp the basics.
For the basics, a few tips I think beginners should bear in mind:
- You need a yaku to win. This is, above all, the most crucial rule for people to focus on immediately. Just having four melds and a pair isn't enough to call 'ron' and win the hand in Riichi Mahjong. You need at least one yaku to do so. It might seem that there's way too many to remember, but most of them are fairly intuitive - if it looks pretty, it's usually a yaku. As a beginner, the important ones to make note of are, using the English names as they appear on that list, Reach, Pointless, No Chi (aka All Pon), Endless (aka All Simples), Dirty Ends, Bonus Tile Pon and Dirty One Suit. That's seven, and it's not too difficult to remember them and use them as a starting point while you're still learning. Be aware that plenty of people use the Japanese names for them (myself included) and the English names usually vary quite a bit as well.
- Don't call tiles because you can. Beginners and people used to other mahjong variants end up calling far too often when they start out, and it's something to learn to control very quickly. Be patient, and be prepared to let tiles you want be discarded without you calling them, because usually it's better for you in the long run. Hands are almost always worth more if you keep them closed (ie. don't 'open' them by calling tiles), and most of the time the only tile you'll need to call will be your winning tile. You can't win every hand, and plenty of hands end without anyone winning, so there's no need to rush. Crucially, calling tiles can often leave your hand without a yaku, because some yaku are only valid closed. Plus, you can only call Reach/Riichi with a closed hand, and Riichi is always a yaku and is a good way to win with a hand that's otherwise pretty bare for yaku. Aiming for a big hand and Riichi is almost always better than just trying to rush out a shitty hand as fast as you can. Only call hands if you need to, such as if you've got a hand that's going for All Pon, or if you are purposefully going for a very quick hand.
- Respect dora and riichi. Both are extremely good ways to make pretty massive scoring hands out of what otherwise would have been pretty crap. A couple of dora generally makes a hand worth quite a large sum of points, and riichi is always at least one more yaku and then potentially quite a few more with One Shot, Strongly Closed and Reverse Dora all possible.
- Don't ignore defence. A crucial aspect of Riichi mahjong is that you can't win of a tile you've discarded previously, so if someone calls riichi or looks close to winning, their discards are an extremely good way to avoid dealing into their hands. Unlike some other mahjong variants, the person who discards the winning tile pays for the entire value of the hand, so dealing into someone's hand is just as bad as winning a hand is good, and many beginners really don't appreciate this fact. If you've got a hand that's shit, don't be afraid to abandon hope of winning so that you can stick to discarding safe tiles. It's much better to just abandon a 2000-point hand and wait for the next round than it is trying to force it out and dealing into a 12000-point hand in the process.
You can register with Tenhou for free, and it'll track your rank and game stats for you. Once you get to 6kyu rank you have to stop using the premium client and use the economy one, but the differences are almost entirely cosmetic and it's not such a big deal.
For game type, I recommend the third one down on the right column, which is Ari, (endless/tanyao is valid open) Red, (uses red dora tiles as well) East+South. East-only games are decent if you're in a rush, but South games are what you should really be playing because luck has far less influence. If you don't like Red dora, choose the second one down. If you feel the play is a bit slow, then pick the fourth one down, which is fast-mode and you get far less time to make each move.
Of course, the most enjoyable way of playing is with other people in person, though mahjong clubs and societies are fairly sparse. For playing with friends, you'll need a set, and for people in the UK I'd recommend this one for being a decent quality set without being too expensive. Getting four people who are keen on a fairly regular basis can be a bit tricky, but there are ways of modifying the rules to play with three people. If anyone around Cambridge is interested, then I'm usually up for playing, and there's the CURMS meets on Friday evenings.
For slightly more advanced PC single-player stuff, I'd recommend Saikyo no 3D Mahjong, which can be downloaded from Rapidshare or, while stocks last, my dropbox folder. It's pretty complicated and entirely in Japanese, but if you click around a bit you can figure stuff out. It's also very customisable for rules and AI, though again, the Japanese makes it a bit tricky to work with. The options screen has been translated into English by Barticle and there's a copy here. There are also various PS2 and DS games and stuff out there, but they can be a bit more obscure, and they're almost always either solitaire mahjong or in Japanese, so probably not the best for an unskilled player without a guide.
Anyway, I hope this was at least somewhat useful as a starting point for the people concerned, and maybe it'll convince a few people to give it a try as well. It's an awesome game of luck and skill, so people should spread the word ;)