Although the USA don't like it, there's a department called INTERPOL which is composed by about 150 countries.
When a crime is committed and you need to involve another country to solve it, the sovereignty of each County prevents a police officer from one country acting upon another country. That's when the INTERPOL comes in. They usually requests the police from that country to act up. A judge from that country will grant their local police access to the data to be delivered to the country that requested it.
Can the police get a search warrant for data 'in the cloud'?
Yes. If the servers are located within the boundaries of your own country, it's a normal procedure. But like the above answer states, it's easier to subpoena the records than to execute a search warrant. In a subpoena, the company itself is bound to provide everything the police asks.
Can the police get a search warrant for such third party systems?
Yes. If there's enough probable cause, the investigation can lead to allow the police to try and discover files that are held by servers that store the cloud data. But if the servers are located outside the country and the company does not have any office opened in the country, a search warrant won't have validity in another jurisdiction and the police can't act without breaking the sovereignty principle. That's where the INTERPOL services are handy. The department is built in the principle of polices from different countries helping each other. The downside is that it's too bureaucratic and it takes a lot of time.
For instance if he has a virtual machine hosted by Amazon, would they serve the warrant on Amazon, or on the suspect?
Like mentioned by @Viktor, if the company has an office within the bounds of your country, it's easier to subpoena the records because that way the company will filter and provide only the data linked to the suspect being investigated. That is, the subpoena will have both the name of the company (Amazon) and the name of the Suspect, so the company can provide only the necessary files.
Update
If the police lack sufficient evidence for a search warrant, but an interpol country was, for some reason, willing to work with the police to collect and provide that information would they be able to use it even if they wouldn't have been able to subpoena a US country?
Hypothetically speaking, I see your follow-up as a company that do have a local office and the Federal Police was turned down by a judge on a warrant/subpoena. In that case, there's no reason for another's country police to act on their own country. The suspect is a foreign suspect, the crime is a foreign crime and the police has no reason to work on it.
But for the sake of argument, let's say that the local police was turned down by a judge for lack of evidence or something and the suspect has been investigated by a foreign country or whatever. If the information that the local police desires to obtain is available through the INTERPOL, it's most likely to be accepted since it's a data stored by an international police department. In your scenario, the foreign police was granted a legal right to search and collected the data for legal purpose. Maybe they can't use it in their own country, but since they followed a safe chain of custody and provided the information to the INTERPOL, that information has legal validity and it is not fruit of the poisonous tree if the chain of custody was maintained.
