Question: I find myself spending a lot of time setting up new servers. I always have the same exact software stack:

nginx
mysql
php + php-fpm + xcache
memcached
munin

I pull all the configuration and init.d scripts from my github repo.

All my servers run Debian. My first step is usually apt-get update and apt-get install vim (and other basic packages).

Would Capistrano or Puppet be capable of automating this process?
If they both are, which one would be more suited for the job?

PS: I would prefer Capistrano because I am comfortable with Ruby.

Answer: 
As far as I know they can. Take note that puppet is ruby too. And so is [chef](http://wiki.opscode.com/display/chef/Home).

I guess it is a matter of personal taste, have a look at the way to define 'recipes' and decide which would better suite you.

You can also look at these [other](https://serverfault.com/questions/96265/puppet-vs-chef-pro-and-contra-from-users-and-use-cases) [questions](https://serverfault.com/questions/42565/floss-server-management-and-audit-tools).

[This answer](https://serverfault.com/questions/9443/production-deployment-tools/9469#9469) says it all :). If you have a git repository already, maybe capistrano is a better choisce.

Check out [these](http://www.agileweboperations.com/puppet-vs-capistrano-short-comparison/) [articles](http://www.agileweboperations.com/puppet-or-capistrano-use-the-right-tool-for-the-job/) about the differences on goals and features of both puppet and capistrano and how to decide between the two.
That does sound like a perfect application of Puppet. If it'll help, I've written a series of short tutorial articles on Puppet for complete beginners, which covers installation, getting up and running, and managing your first Puppet resources:

[Puppet tutorial](http://bitfieldconsulting.com/puppet-tutorial)