@maxdog,
To whom do you refer with "they" in your post?
The type of agency which carries out maritime search and rescue varies by country; it may variously be the coast guard, navy or voluntary organisations. When a distressed or missing vessel is located, these organisations deploy lifeboats to return them to land. In some cases, the agencies may carry out an air-sea rescue.
I don't know exactly how it works in other countries, but Search and Rescue in German waters is conducted by the German Maritime Search and Rescue Service with air support by the German Navy and the German Air Force. The German Coast Guard (Federal Police, Maritime Customs Service, various state s' water police units, ...) provide SAR services, too.
If a cruise-liner sinks, the first to help would be the ships close to it.
And since cruise ships use the normal sea routes, there will be quite a few nearby.