Even as wireless networks create the potential for access to information from mobile platforms, they pose a problem for privacy. In order to retrieve messages, users must periodically poll the network. The information that the user must give to the network could potentially be used to track that user. However, the movements of the user can also be used to hide the user's location if the protocols for sending and retrieving messages are carefully designed. In this thesis, we will present a protocol for a replicated memory service which allows users to read from memory without revealing which memory locations they are reading. Unlike previous protocols, this protocol is efficient in its use of computation and bandwidth. We will then show how this protocol can be used in conjunction with existing privacy preserving protocols to allow a user of a mobile computer to maintain privacy despite active attacks. Allowing users to retrieve messages anonymously introduces a new problem. In order to limit memory usage, it is necessary to remove old messages from the system. However, since users may become disconnected from the network for periods of time, it is important that the system hold onto messages until they have been retrieved by their intended recipients. The result is a conflict between the system's need for information and users' desire for privacy. We will present the design of a vacation service which we have developed which stores messages for users which are disconnected which does not require users to reveal any private information. Finally, we will describe the implementation of the private message service and discuss the performance estimates that we derived for the system based on experimental results. As we will show, the potential throughput of the private message service is reasonable.