There are many styles, but I personally find it very helpful to have one comment per class (describing the class in general terms), and one comment per method, which lists input parameters, result, and any pre- and post-conditions of the method.
I would recommend you use some template system. In Java that would be Javadoc, in C++ et. al something like Doxygen. That way, your comments can be automatically parsed, formatted as separate documentation or extracted by the IDE, and checked for completeness / consistency (e.g. undocumented parameters).
As a bonus, there are checkes available (e.g. built into Eclipse) that will highlight incomplete/missing docs.
If you have complete coverage of such docs, then you have a very well documented codebase.
As to inline comments, I would use them very sparingly (if at all). The rule of thumb is: If you need inline comments, then your code is too complicated, or your method is too long.
The only exception I can think of is code that is impossible to understand without knowledge external to the code. Examples would be implementation of complex mathematical algorithms, tax calculations, internal business rules, or non-obvious workarounds for bugs in a system you need to interface with.
Even in these cases, inline comments should be few and brief. If that is not enough, refer to external documentation for things like algorithm details.
As to where to start: It does not really matter. Usually a combination of top-down and bottom-up makes most sense. Ask around which part people feel is most in need of documentation (or which was the source of most bugs recently). If there is nothing to guide you, just pick something.
The same goes for being exhaustive or not. You can start by just writing class comments (less exhaustive), or completely do one class with all methods (more thorough). Decide based on criteria above.