Methods and apparatus for communicating information, e.g., queries and query responses, in a peer to peer communications network are described. Queries include, e.g., queries for a product, service, activity or activity partner. In some embodiments, a query channel is implemented and utilized. The implemented query channel structure is such that multiple query responses may be communicated corresponding to a single transmitted query. Various embodiments employ randomization in transmission segment selection by an individual communications device within a transmission block to decrease the likelihood of collisions. A communication device's access to the query channel is determined by the communications device itself. A communications device's decision as to whether or not to transmit and/or re-transmit a query is based on one or more of: its query transmission statistics, historical query channel loading information, and priority level information corresponding to the communications device.