First, how is the story in this game? Is it rich, in depth, etc.? And the description on this site says the skill system is based around "learning by doing" - What does that mean?

The story is, hmm I wouldn't call it rich, or in depth. There aren't a lot of NPCs that you can talk to, usually up to 3 per location. The dialogues are well written in my opinion and convey a lot of the atmosphere of the game (quite depressing at times). Most of the time that you spend in the game, you'll be exploring the locations, on your own. The creature design is a masterpiece in my opinion, this game has some really unique enemies and NPCs that you can come across, you can meet the other adventurers that you didn't choose at the beginning, too. So, the game is more about the atmosphere, exploration, solving puzzles (several quite nasty) and fighting. You can look up the "dungeon crawler" to get a better feeling of what kind of cRPGs are they. This game has richer story than usual dungeon crawlers though.

Yes, you acquire skill points by using weapons and spells. You assign those points however you want (weapons and magic skills are separated) after leaving the location to the "outside world".