It seems almost daily now, I have discussions about non-functional requirements in agile. How do we get them into the backlog? Are they stories like "As a developer, I can run tests so that I know if I coded it wrong"? What about when we realize that we're storing the users password as a cookie to make it easy for them to log in, and the CSO issues the sermon of "thou shalt not store passwords anywhere..." Do we add another story that says "As an application, I have to get the password interactively from the user on login so that I don't give the CSO a stroke."
Non-functional requirements are not the same as user stories, so don't try to shoe horn them into the process. They are never 'done' in the sense of a user story, because they are implied on all features of the product and must be implemented as such. Non-functionals are defined in the team's "Definition of Done" which must be driven by a clearly defined quality model that is shared between all developers, QA, architects, UE/UX and owners alike.
The quality model defines specific areas that a feature which is "done" must conform to. You don't even have to come up with your own, there are lots of these on the web, a quick wikipedia search will refer you to a number of really well written documents that all really point back to an ISO standard of quality which contains Reliability, Usability, Security, Efficiency, Maintainability, Portability and a few others. All of these items have to have targets and benchmarks for how your software will be written. All projects should start with this definition, which is hopefully standardized within your organization to some degree.
Once you have this definition of done agreed to by all parties, then you can keep you backlog a pristine list of features that your customers will love and not muddy it up with techno-babble about performance tests, deployment support, accuracy, yada yada yada. All your stories will have tasks to address the quality aspects of your features and the team will take these into account during the planning of each sprint.