The guarantee is theoretically possible if it's a money-back guarantee or some kind of performance-based payment system. For instance, if you don't get to no. 1 for X competitive keyword within 6 months, they give your money back or 50% off or something. No one can guarantee how high a page goes on Google or any other search engine they don't own, because the search engines are all run by companies that have interests other than helping out SEOs or website owners--like pleasing the people who use them to find the most relevant sites.
What often happens, as the other posters here are implying, is that an SEO company will guarantee no. 1 rankings for a very uncompetitive term, i.e., a term that no one or hardly anyone ever searches on, and whose number-one result currently is not competitive (low PR). I could guarantee you number-one rankings for "dog grooming products anchorage alaska" or something like that. Most often the people who buy into these things are complete idiots at least in the field of web business, and are satisfied when they get to number-one for their business name or some uncompetitive keyword, and just curse the internet when they don't get customers.
As for how do you get links on high-PR pages: it's simple, you buy them. There are sites like linkworth and textlinkads that facilitate these sales. For a prominent link on a well-trafficked, highly relevant PR6 or above homepage you are easily looking at $1000/month, though truth be told you might be paying that much in pay-per-click charges if you used Adwords to get on that page.
You can also get a link on a PR 6 webpage, at least temporarily, by blogging. Many blog homepages have PR 6 and many of them will put a full post on the homepage, which often includes links to other websites.
