We consider efficient techniques for delivering audio-video telephony/conferencing service (AVS) traffic over WiMAX networks. Issues that need to be considered in error-prone and variable delay wireless networks specifically for real-time AVS traffic include delay, jitter and the possible lack of synchronization between audio and video traffic. First, we consider two different schemes for WiMAX connection management that allocate the same connection ID (CID) or two different CIDs for audio and video connections, which we refer to as integrated-CID scheme and separated-CID scheme, respectively. The integrated-CID scheme is amenable to connection management with reduced overheads, but causes cell-edge users to suffer longer voice delay variance. Second, we consider two different audio codecs, with low and high source rates. Generally, a codec with a high source rate gives more satisfaction to users, but we show that this does not hold for cell-edge users because it breaks the synchronization from video frames due to the longer reception delay. Finally, we investigate appropriate strategies for codec selection for both cell-edge and cell-interior, i.e., selecting a combination of high-rate audio/low-rate video and low-rate audio/high-rate video. We conduct simulation experiments to test the proposed scenarios over mobile WiMAX systems.