Hi. We came from the UK with our dog 2 years ago and it was quite easy. We needed an DEFRA export health certificate (ring DEFRA and they will send one to your vets office), he needed to be up to date with his vaccinations and he had a rabies jab. We knew he did not necessarily need the rabies jab but thought it would just be easier all round if we did it. I think it had to be done within 2 weeks of travel though - I can't remember exactly. Not sure if you need this for cats?
Regards the actual trip, we simply booked him onto our Air Canada flight with us. We checked him in at oversize baggage (where you would take skis, golf clubs, buggies etc) in a crate (has to be certain size/specification for each airline) and collected him at the other end. We then had to go through the Agriculture desk at Vancouver airport and pay the inspection fee ($35 IIRC) and we were good to go.
I would advise looking on the CBSA website to see if you can find up to date info there and also contact the airline you will be flying with.
Hope this help
Amanda