since I am new to Perl, and haven't touched C
monks -- I think our suggestions are probably a bit over Leon's head right now. Maybe we need to take a step back here.
Leon -- first off, I'd recommend you get some books and learn Perl and C at least at an introductory level. Perl XS isn't going to be covered in those books, but you'll need the knowledge. Also, you'll need to understand C -- and since you haven't got a solid grasp on C yet -- I'm expecting even makefiles might be foreign to you. Perl is Unixy by nature, and so is C, so if you have neither this may be a hard road.
Not to jump to conclusions, but I think you have bit off more than you can chew, and maybe, just maybe, you aren't the right person for this job? Your managers, etc, would probably be appreciative if you made them aware of this (what you still need to learn and what you are not familiar with), otherwise they will be knocking our your door later wondering where the code and is and why you are encountering problems. Can you get some Perl and C programmers to help you? Where does your expertise lie if you are doing Perl and C and aren't proficient at either? (i.e. how did you get drug into this?) Can you operate the C debugger if you must debug a C module? Are you prepared for the evils that may go wrong (seg faults, core dumps, pointer problems, etc)?
I'm just saying this because XS is not the first thing someone does with Perl, and XS with C code requires, pretty much, that you understand C. If you must trudge forth, Inline::C will get you started and perhaps it can be written in XS later once you get the other quirks cleaned out.
Also, rather than asking for someone to step you through this, perhaps you could post the docs you have looked at, and the monks can recommend some other references? Many of us would probably like to offer pointers, but we can't devote time to a 1:1 if that 1:1 is going to include multiple lessons on C basics, makefiles, and other non-Perl prerequisites (IMHO) that you need to do this particular job.