Despite their apparent use of the English language, Canada has the most confusing immigration/border information web site I have ever seen. Fortunately, I have a little experience with this (having had to be deemed rehabilitated myself, and having friends who had to go through the rehabilitation process) and the actual processes are quite a bit simpler than the web site makes out.
If it's been less than five years since your probation/parole ended, you're considered inadmissible to Canada, and can't apply for rehabilitation.
The temporary resident permit, however, overrides this inadmissibility, usually for a single entry. It can be granted by a consulate, but for Americans who receive one it's almost always issued at the border, and the Americans involved are usually quite surprised that their old criminal record makes them inadmissible.
The guidance states that in order to receive a temporary resident permit, "your need to enter or stay in Canada must outweigh the health or safety risks to Canadian society, as determined by an immigration or a border services officer." This gives the CBSA officer fairly wide latitude in determining whether to give you one. Your ability to articulate and represent yourself well will be quite helpful here.
When you're issued a temporary resident permit at the border, you will be told how long you are allowed to remain in Canada, and you will be instructed that you must check in with CBSA at the point of departure. Since Canada does not have exit immigration, you have to go out of your way a bit to visit the Canadian port of entry at your border crossing when you leave and have someone there verify your exit from Canada. You will be instructed that if you don't do this before the end of your allowed stay in Canada on the temporary resident permit, an arrest warrant will be issued for you.
You can, if you wish, apply for the temporary resident visa from a consulate. Note that this is the same type of visa that all non-immigrant Canadian visitors receive for tourism, business, transit, or study. But if you haven't been through the rehabilitation process, you are likely to be refused without a very compelling reason for visiting. Going on a cruise probably won't qualify.
You can also just take your chances and show up at the border. It's possible your criminal history won't be checked and you'll pass through without a hitch. If you're on a US passport, passport card or enhanced driver license, it might not even be scanned. But if you're asked about criminal history, you should go ahead and disclose it, since they can access it anyway, and lying will only make the situation worse. Since you're merely transiting, you may be allowed to go on with a temporary resident permit. In the worst case, you would be detained and removed back to the US (which is where you were going anyway).
