What are the possible ways they can do that?
The main ways police can obtain search records are by:
Looking at local browser history on the suspect's computer (as you mentioned).
Demanding connection logs from the ISP, revealing what sites have been visited.
Demanding connection records from the sites that you have visited.
Demanding search records from search engines, such as Google.
Is it possible for ISPs to have access to that kind of information? My understanding is that anything over SSL isn't easy to decipher unless there is some kind of MITM attack.
TLS encrypts web traffic, however you still need to know the IP address and domain in order to connect to a website over HTTPS, and this information is sent in the clear. When connecting to this site for example, your ISP sees the IP address of stackexchange.com, and SNI also gives away the subdomain (security). Your ISP will not know exactly what pages you viewed, however. See another question for more information on what exactly TLS protects. More specifically:
https://subdomain.example.com/some/path?with=stuff
| visible to ISP | encrypted |
If subdomain.example.com is incriminating, then TLS will not protect you. If the rest of the URL is incriminating, then TLS will protect you from ISP snooping but will not protect you if a court order demands the connection logs from example.com. Only an anonymity network, such as Tor, can help prevent this by disassociating your real IP from the IP connecting to the websites.
Does using a Tor Browser prevent these other ways?
Yes, Tor Browser prevents this type of snooping because everything between you and the exit node is encrypted. The EFF has a great explanation of Tor and HTTPS. When using both, you can use this diagram to see exactly what different adversaries are able to see and from what position when you are using Tor and HTTPS together.. It is helpful to use this to develop your threat model.
The diagram looks a little different if you are using Tor without HTTPS. While Tor still prevents your ISP from seeing anything other than the fact that you are using Tor, the exit node will be able to read the traffic (but it cannot tell where it came from). This can be an issue if you are submitting sensitive credentials over Tor to a website without using HTTPS. Check out the EFF link to see an interactive version of the diagram where you can toggle Tor and HTTPS status.
One important thing to remember is that Tor is only a tool and, like all tools, you can use it wrong. It will not help you if you screw up and post bomb threats to your school while you are the only user of Tor at the time. Likewise, Tor does not prevent you from accidentally revealing PII.
