I can't point you to any great examples out on the web at the moment, aside from Aslak's cucumber wiki on github. I can tell you a little bit about how our cucumber style has developed.
In our experience there are two main directions you can follow with cucumber stories. The path on which we started with was high-level implementation-independent user-story-style steps. For example:
Given the user has entered an email address that belongs to an existing user
And the user supplies the correct password
When the user attempts to sign in
Then the system signs the user in
And the system displays the welcome page
And the system displays an indication that the user is signed in
As we've evolved our use of cucumber, we've moved away from this style (which lends itself to the feature-coupled steps anti-pattern) towards a more user-interface-specific set of steps that relies as much as possible on the pre-defined webrat/culerity steps. For example:
Given I fill in "Email" with "[email protected]"
And I fill in "Password" with "tr33fr0g"
When I press "Sign In"
Then I should see "Welcome, Kaspar"
The advantage of the former style is that it can be written without any knowledge of the interface, and is relatively robust in the face of interface changes. The advantage of the latter style is that it feels less prone to analyst writer's block and makes it even more unambiguous how exactly to proceed as a developer writing code.
Lakshan Perera's Extended Bort revision of the Bort example app includes the cucumber plugin, but unfortunately no examples.
I'm hopeful that the RSpec book forthcoming from Pragmatic Programmers will provide some fleshed out examples.