They do not use visited URLs. While Firefox separates its location and search bars, this seems to me more of a design choice than a privacy one. I could be wrong! - but then again, the much bigger privacy risk is using Google in the first place, and if you switch to a different search engine then Google stops receiving autocomplete too.