I don’t think anyone took a phone book with them. This is the first time I’ve ever heard it suggested.
My Father had a ‘car phone’ from 1990-1999ish and then switched to a nokia 3210 or similar. While he had the ‘car phone’, he kept a phone book in the car. By the time of the Nokia, his outbound calling was predictable enough that he either had it saved on the phone or he used ‘411’ to have an operator look up the number.