It will need to be installed on each node, but it can be automated.
If you are using Puppet Enterprise, just need to run
curl -k https://<master hostname>:8140/packages/current/install.bash | sudo bash on each node.
If Puppet Open Source, just need to add the repo ( for example,
$ sudo rpm -ivh http://yum.puppetlabs.com/puppetlabs-release-el-6.noarch.rpm if on RHEL6 or a derivative or
$ wget https://apt.puppetlabs.com/puppetlabs-release-precise.deb && sudo dpkg -i puppetlabs-release-precise.deb && sudo apt-get update if you are on Ubuntu 12) then instal the
puppet package using apt or yum. You can find more detailed instructions here.
With both of these methods, the actual automation would come from mostly likely, ssh and a for loop.
For new nodes, you would add the package installation to your provisioning process.