Methods and apparatus for efficient two-stage paging wireless communications systems are described. Wireless terminals are assigned to paging groups. A few first paging message information bits are modulated (using non-coherent modulation) into a first paging signal and communicated from a base station to wireless terminals. WTs wake-up, receive the first paging signal and quickly ascertain whether its paging group should expect a second paging signal, if so, the WT is operated to receive the second paging signal; otherwise, the WT goes back to sleep conserving power. The base station modulates (using coherent modulation) a number of second message information bits into a second paging signal and transmits the signal to WTs. From the information in first and second paging signals, a WT can determine that it is the paged WT and process the paging instructions. The intended paged WT can transmit an acknowledgement signal on a dedicated uplink resource.