In Pages you can create links in documents that remain if you save the document as a PDF.
As for addking links to existing PDFs, I'm not sure what to suggest other than Adobe Acrobat which is a rather expensive option.
This seems like a rather glaring omisssion from Preview. I really think it's a mistake as even the Help file for Preview refers to creating links.
I'm betting this gets resolved.