The Specification By Example book states the non-functional requirements (commonly referred to as NFRs) can be specified using examples.
I've also been told by a colleague that non-functional requirements may be specified using SBE stories using the format:
Scenario: ... Given ... When ... Then ...
Here is an example functional and non-functional requirement taken from wikipedia:
A system may be required to present the user with a display of the number of records in a database. This is a functional requirement. How up-to-date this number needs to be is a non-functional requirement. If the number needs to be updated in real time, the system architects must ensure that the system is capable of updating the displayed record count within an acceptably short interval of the number of records changing.
Question 1: Can the non-functional requirement be specified as a story?
Question 2: Should the non-functional requirement be specified as a story?
Question 3: What would the story look like?
Q1: Yes, definitely they can. Take a look on that article describing Handling Non Functional Requirements in User Stories.
Q2. From my perspective if you able to create them it's really worth of keeping and tracking them in such a way. But citing this article
There is no magical agile practice that helps you uncover NFR. The first step is to take responsibility. NFR can be represented as User Stories if the team finds a that this helps to keep these visible. However, be aware that surfacing such stories may create issues around the priority of work done on them against more obvious features.
Q3. Take a look on the mentioned article from Q1.