Have a look at these articles by Steven McDougall. They did help me most of all:

http://world.std.com/~swmcd/steven/perl/pm/xs/intro/

Quote:

This article is about XS. It explains what it is, why it is, how it works, and how to use it. It includes a complete, working example of an XS module, and a stub module that you can use as a starting point for your own code. It is an express goal of this article to provide the background and information necessary for you to write your own XS modules.

This article is in five parts

November - Introduction motivation, definitions, examples
December - Architecture the Perl interpreter, calling conventions, data representation
January - Tools h2xs, xsubpp, DynaLoader
February - Modules Math::Ackermann, Set::Bit
March - Align::NW Needleman-Wunsch global optimal sequence alignment