Last updated February 19, 2013.
There are four issue priorities used on Drupal.org, this page describes how they are used in the core issue queue, usage may vary across contrib projects.
Critical bugs either render a system unusable (not being able to create content or upgrade between versions, blocks not displaying, and the like), cause loss of data, or expose security vulnerabilities. These bugs are to be fixed immediately.
In Drupal 7 this also applies to test failures in the primary environment: we have a policy of a 100% pass rate for tests, so failing tests block all other development. The primary testing environment is currently MySQL on Linux. Tests failing in other environments should be marked as major.
Major versions of Drupal core (like 6.0 or 7.0) won’t be released until all critical bugs are fixed. For point releases (like 7.1 or 7.2), outstanding critical bugs won't necessarily hold up a core release. If there are 20 critical issues when 7.2 is released, and five of those are fixed, then it may make sense to release 7.3 with the other 15 critical issues open - or there may be a security release that has to go out anyway.
In contributed projects, it is up to each maintainer how they handle the critical status.
Issues which have significant repercussions but do not render the whole system unusable are marked major. An example would be a PHP error which is only triggered under rare circumstances or which affects only a small percentage of all users. These issues are prioritized in the current development release and backported to stable releases where applicable. Major issues do not block point releases.
In Drupal 7 this also applies to test failures in secondary environments.
Major priority is also used for tasks or features which consensus has agreed are important (such as improving performance or code refactoring), but which are not functional bugs.
Bugs that affect one piece of functionality are normal priority. An example would be the category filter not working on the database log screen. This is a self-contained bug and does not impact the overall functionality of the software.
Minor priority is most often used for cosmetic issues that don't inhibit the functionality or main purpose of the project, such as correction of typos in code comments or whitespace issues.
Choosing the right priorities
Tasks and Feature Requests are very rarely “critical”. They should usually be “normal” or “minor”.
Support requests should never be marked 'critical' or 'major' - if you believe you have run into a bug and it is preventing your site from working at all, post it as a bug report, however be prepared for other Drupal.org users to recategorise it as appropriate. The more-urgent priority is unlikely to give you better support; it is better to describe your issue thoroughly to help people understand what is wrong.