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.
As far as I know they can. Take note that puppet is ruby too. And so is chef.
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 questions.
This answer says it all :). If you have a git repository already, maybe capistrano is a better choisce.
Check out these articles about the differences on goals and features of both puppet and capistrano and how to decide between the two.
Puppet would be ideal for this. Puppet provides you with a declarative language to describe the configuration of each server, including packages, services and configuration files. Puppet provides a strong framework to describe the dependancies that each component has on each other, which allows your to build modular configuration files that describe how to take a base image and turn it into a server ready to handle a particular role.
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