We study caching as a means to reduce the message traffic and database accesses required for locating called subscribers in a Personal Communication Services (PCS) network. The challenge of caching routing information for mobile clients lies in the uncertainty of the length of time that the information remains valid. We use expiration timestamps to safeguard against using stale cached data. We study a variety of caching algorithms and a variety of methods for setting timestamps based on client mobility. We report results from simulation studies.