This paper investigates empirically design issues in auditory information processing, relevant to interfaces for mobile telephony. This investigation forms the initial part of a larger experimental program, which aims to investigate design methodologies for auditory-multimedia interfaces. Structured musical and environmental audio was used to communicate simple and complex (i.e., larger amounts) information for mobile telephony.The contribution of this paper is in the empirical investigation of the perceptual principles involved in using auditory stimuli to communicate information rather than the mere application of sound in this problem domain. Some of these experiments also aim to communicate information that would normally be communicated using the visual displays of mobile devices.Results indicate perceptual issues that need to be considered in the design process of auditory interfaces. Memory demands on users may in some cases prevent the correct interpretation of the auditory stimuli. Other issues observed to help the designing process of auditory user interfaces include the creation of perceptual context, semantic coding and auditory user interaction model.