Techniques are described for performing actions for users based at least in part on spoken information, such as spoken voice-based information received from the users during telephone calls. The described techniques include categorizing spoken information obtained from a user in one or more ways, and performing actions on behalf of the user related to the categorized information. For example, in some situations, spoken information obtained from a user is analyzed to identify one or more spoken information items (e.g., words, phrases, sentences, etc.) supplied by the user, and to generate corresponding textual representations (e.g., via automated speech-to-text techniques). One or more actions may then be taken regarding the identified information items, including to categorize the items by adding textual representations of the spoken information items to one or more of multiple predefined lists or other collections of information that are specific to or otherwise available to the user.