convert xyz.png xyz.pdf deve fazer o truque.
Veja man convert para mais opções.
Abrindo um arquivo png no Ubuntu, eu posso ver o item de menu para 'imprimir para arquivo'. Como posso fazer o mesmo no shell? PS: Eu prefiro não instalar nenhum pacote extra, devido à falta de acesso root.
EDIT: o sistema operacional é o Ubuntu 11.10
convert xyz.png xyz.pdf deve fazer o truque.
Veja man convert para mais opções.
Se você quiser converter várias imagens , por exemplo arquivos png, em um único pdf usam convert com o nome de arquivo pdf especificado no final
convert *.png mydoc.pdf
Ele mesclará todos os arquivos png em um arquivo sinlge mydoc.pdf em ordem descendente.