Methods and apparatus for efficiently communicating network connectivity information in a communications system are described. Two types of signals with different characteristics, e.g., long range synchronous beacons, e.g., LTE-D beacons, and short range asynchronous beacons, e.g., WiFi beacons, are used in combination to advertise network connectivity information and accelerate the acquisition of a routing path for a communications device to a device serving as a gateway for a infrastructure network. Reception of a first type signal triggers monitoring for a second type signal, and a received second type signal communicates information used to determine a communications path to a gateway device.