Run on start: Up to the user. They will put it in Login Items if they want it to run on start. You can add a button to add it to Login Items automatically; use Launch Services' Shared File List API to add it to the Session Login Items list.
Menu bar item: This is called a status item. See NSStatusItem.
Checking for caps lock: First off, there may be multiple keyboards, most of which will have a caps lock, and not all of which will have the same caps lock state (the user may have one with it on, one with it off, and a third with no caps lock key at all). Pay attention to each keyboard's caps lock state separately, and light up your indicator if any caps lock key is on.
To read and monitor the caps lock keys, you'll need to dip into I/O Kit. I believe you'll need to use the HID Manager. That's a C API, but Dave Dribin has written an Objective-C wrapper for its lower-level predecessor (most recently at 1.0.1).
Edited to add: You can monitor caps lock using a Quartz event tap, but it's not per-keyboard, so I'm not sure you'll get reliable results with multiple keyboards, and it still won't let you read the initial state of the caps lock keys when your app launches.