The magic in Erikson's books is via things called "Warrens", which are a channel for magic, and can also be used to travel through, they shorten journeys considerably.
There is also a lot of tribal magic and such. All in all, the magic is one of Erikson's strong points
The first book in the "Malazan Book of the Fallen" series is "Gardens of the Moon". Malazan is the only fantasy series Erikson has written, though he has previously published under his real name, Steve Lundin. In the "
Bibliographie - Steven Erikson" thread, there is a full list of his published (and still to be published) books and novellas.
Erikson is constantly compared to Martin, as there are the two leading traditional fantasy writers around at the moment by a long shot, but in reality they are very different writers. "Gardens" does put a few people off Erikson, becuase it is not the best written of books if you need to know whats going on in books that you read. My advice to you would be just let any confusion wash over you, and enjoy the books. It'll all be explained in good time