This comes straight from the link you gave on CPAN...

*mutter* Weel, then that tutorial needs updating then (a thousand cpan authours don't write tests and Makefile.PL's for nothing -- that's why I pointed to A guide to installing modules initially, it's a better tutorial).

Or maybe saying I missed .xs file and therefore missed the build step?

I thought this was obvious (you did miss the .xs file).