Selectors are the internal representation of a message, used by the underlying machinery when sending a message to an object -- i.e., method calls are transformed into objc_msgSend() calls, where the arguments are the object being sent to, the SEL (selector) of the method to execute, and then any arguments for the method itself. You'll see selectors in code most often when you're providing a callback method -- for example, when setting the target and action to be called on a button click, the target is the object to call and the action is the SEL of the method to call. You can use the method -performSelector: (or one of the variants) to send the message represented by a SEL.
Categories simply put are a way to add methods to an existing class. When a category is loaded into the runtime, the methods are added to the method list for that class, so there's no difference between category methods and methods implemented in the base class.
This ability opens up a bunch of possibilities.
As noted, you can use them to break apart a really big class into separate files, so each file is a more manageable piece.
Most often, they're used to add functionality to existing classes when that is the natural class for the functionality in question. This is usually better than subclassing solely to add generic functionality, since you don't have to convert objects into your subclass just to call methods on them (the methods are now on the original class itself), and also since it does not add conceptual complexity by having extra subclasses that essentially serve the same purpose as their superclasses. They are also usually better than external functions (or Java static methods), since it keeps things object oriented -- i.e. they are real methods that can be performed, overridden, etc. as needed. The Omni frameworks have many examples of this kind of stuff.
Categories can also be used as glue in certain situations. Say FrameworkA defines a protocol (same as a Java interface) that it wants objects it works with to implement. You're also using FrameworkB, which produces objects of classes that it defines. These objects fit very naturally for use by FrameworkA, but since they don't implement the protocol in question, you can't use them directly. In Java you're stuck, but with categories you can simply implement a category on the class(es) from FrameworkB that implement the protocol from FrameworkA (you can even declare the category as officially conforming to the protocol), at which point you can then use the objects directly with FrameworkA. Simple and clean, this solves the problem with a minimum of code, no additional classes (conceptual complexity), and no runtime performance penalty.
You can implement a class in one framework, and use categories to extend it in a higher-level framework with functionality specific to that higher-level framework. For example, the Foundation framework has NSAttributedString, a generic attributed string. The AppKit framework declares several attribute types specific to AppKit, and with categories adds a bunch of methods using those attributes. Similarly, you can have a class implemented as a framework, and add categories in an application that uses that framework, if the methods in those categories are really only useful from inside that application. Things stay object-oriented, but the original class isn't cluttered with methods that are only useful in very specific circumstances.
If you want to get really powerful, you can add methods to the NSObject class, at which point *every* object will now have that method. The stuff in NSKeyValueCoding used to be in a separate framework; a category was added to NSObject for the base implementations, and additional categories added overrides for NSArray and NSDictionary. There are other examples of this sprinkled throughout Cocoa as well.
Categories are not completely risk-free, however. Since you're adding methods to a class, there is sort of a "namespace" in that class -- if you add a method with the same name as an existing one, only one of them will "win" and be used by the runtime. Given the possibilities of method names, this is a fairly rare thing to have happen accidentally -- and even if it does, the likelyhood that is two methods named the same thing perform the exact same functionality. If they don't though, these problems are among the toughest, time-consuming, and frustrating bugs to track down.
If you're wondering which "wins", it's whichever method gets loaded into the runtime last. A method in a category will override a method in a base class, since the base class is always defined first. [This trick can be used to fix bugs and the like by creating a category with a fixed version of a method. It is very difficult to invoke the original implementation in theses cases though so I wouldn't recommend doing this unless it's a temporary quick fix.] If the two methods are *both* in categories, it's officially undefined which one wins. In reality it's dependent on the link order of the original compilation, but this is an implementation detail that you most definitely can't count on.
Because of the above, you might want to think a bit first before adding category methods willy-nilly. If you're just writing an application, or a framework that's meant to be used with known applications, then go right ahead -- if any problems come up you can just change your code.
If you're writing a reusable framework, then think about them much harder. If they're providing functionality based on your framework, fine. If they're just generic functionality that you need in your internal implementation, then think about making them public (i.e. declared in a public header) so your end users have a heads-up, think about making the method names contain a string related to your framework name to reduce the likelyhood of name collisions (*especially* if they're not public -- prefixing them with underscore is also a good thing to do), and even think about making them internal functions (static functions if they're only used in one file). Otherwise, you're increasing the likelyhood of causing name collisions for people who use your code. Be especially wary of adding methods to NSObject.
That said, the immense utility of categories far outweighs the (very) occasional problems they cause, especially given that most of the time you're not writing reusable frameworks :-)