Apparatus, and an associated method for facilitating paging of an access terminal operable in a radio communication system. A paging message is formed that includes partial identities of access terminals that are to be paged. The partial identities are arranged into groups of partial identities. And, the groups are ordered. Ordering of the groups conveys additional information bits.