We have a ticket open to make criteria a plugin so they can be added easier and shared via the plugin database. The code is written and just needs to get tested and integrated. Because it is an API change and requires database changes it will go into 2.6 rather than a 2.5 point release.
We will write a plugin authoring guide once the final format is confirmed.
At the moment it is possible but not particularly easy. You can see what you need to change in the first comment in the tracker issue above. Be aware though that if you write new criteria for 2.5 you'll have a little work to port it to the 2.6 format (it shouldn't be too hard but there are some changes).