Además de lo mencionado, PDFjam incluye una herramienta de línea de comandos, pdfnup que hace esto. (Hace uso del paquete pdfpages para PDFLaTeX debajo, que también puede usar).
Si prefiere una GUI, jPDFtweak es otra opción.
Usar pdfnup:
$ pdfnup file.pdf
Esto creará un nuevo archivo pdf exactamente como lo solicitó.
Esta es una pregunta lo suficientemente antigua como para pensar que las opciones que tenemos ahora estaban ausentes en ese momento, pero tal vez merezca una solución actualizada.
Los visores de pdf de Linux suelen utilizar las opciones/propiedades de impresión para configurar el diseño de la página, y allí puede imprimir varias páginas por hoja/lado. La idea es usarlos para imprimir en un archivo como PDF .
Evidencia puede hacerlo, también qpdfview . Más aquí.
vista qpdf
Evidencia
Visor de PDF Studio
Otros lectores de PDF deben tener opciones similares.