Use the Search All Work Items prompt at the top right hand side of Rally. The search page will show if the story is in an Open Project, Recycle Bin or Closed Project.
If a story is not found, it may be that your ID does not have access to the project where the story is located. You can engage your Workspace or Subscription Admin to perform the search to eliminate access issue.
If the missing story is a child story and the parent story was deleted, the child would not appear in the recycle bin. When a parent story is deleted, it is sent to the recycle bin with it's children, but the child stories are not visible there. The only way to know would be to restore the user stories from the recycle bin, and see if the user story you are missing is restored with them as well.
If you know an item the story was associated with, check the revision history of that item. For example, if your user story was part of an iteration, you could go to Plan > Iterations > click on the Iteration name and select the Revision link to look for entries such as:
Unscheduled User Story [US1: Name (Moved to Recycle Bin)]
This row will also provide you with the date/timestamp as well as the individual who performed the action.