After some research I found out that I need to install XCode provided by Apple. Now here's the caveat: latest version of XCode (XCode 4 at the time of this article) is only free with Lion and Mountain Lion (the latest OSX versions). I currently run Snow Leopard and didn't find it fair to pay money to get a simple compiler. More research and I found out that XCode3 is still free for Snow Leopard and earlier releases. This is the link to download XCode3. Sign in with your Apple ID and you're set - you will now be officially registered as an Apple Developer. Woohoo.
This is the file you need to download. Notice that it is around 4GB:
Alternatively if you want to save some time and space, you may want to just download the following kit which is around 700MB:
After installation is complete you should be able to use make, gcc and compile whatever Perl module you want!