User stories and use cases are both used to document the requirements from a user's perspective. There are some similarities. For example, they both capture features of the system. They're both used by the development team to construct the best solution. They can both be used to organize and categorize requirements. And they can both be used as references during testing to ensure that the requirements have been met.
But they also differ in substantial ways. Use cases and user stories accomplish very different goals. They uncover different levels of detail. And they are generally used at different points in a project and different points in the requirements lifecycle.
A use case goes into significantly greater detail than a user story. Use case documents (also called "use case specifications") can be many pages long, so using an automated traceability or requirements management tool to manage the sections of a use case rarely displays all the key pieces at once. Use cases capture the details of an interaction between the user and the system, and good use case specifications leave no stone unturned.
A user story is a shorter, more precise statement about what user X wants from system Y, and includes the business value Z associated with the interaction. The user story can be stated as "I (in my role as X) want the system to do (Y), so that (Z)." These "stories" are concise enough to fit on a single 3x3 sticky note or 3x5 index card, so you will sometimes hear them called "requirements cards." They do not include detailed business rules, data specifications, usability standards, or any other detailed requirements beyond a simple description of the feature itself.
The difference between use cases and user stories becomes very clear when we look at their purpose. A use case captures the detailed requirements of a user/system interaction, with the primary purpose of handing it off to the development team who will develop the solution. In contrast, a user story captures high-level requirements without going into details that might be changed later, for the primary purpose of identifying features and their associated business value, so that they can be prioritized appropriately.