Methods and apparatus related to peer/network/service discovery in a mobile wireless system, e.g., an ad hoc peer-to-peer network are described. Transmission of discovery information, e.g., upper layer discovery information, is divided into a number of portions to be transmitted separately over time. Transmission of the individual portions is structured so as to enable flexibility in the frequency of the peer discovery transmissions as well as the monitoring of such transmissions. Various embodiments facilitate rapid discovery and/or secure discovery, e.g., selective discovery by trusted peers.