Drazen offers excellent advice.
I've been in your shoes, and took the same journey. Here's what I did, in order:
1. I took an AMA course in maintenance management. It didn't answer all my questions, but it provided a system to follow.
2. I bought the CMA's (Chemical Manufacturers Association) set of "Mechanical Integrity Program Development" manuals. They answered most of my questions, because it basically walked you through step by step on how to develop a maintenance program geared toward satisfying CFR 1910.119, Process Safety Management. Everything Drazen wrote was covered in these manuals. It even came with its own complete sample maintenance program: development material, scheduling and priority matrices, procedures, forms, etc.
3. I scheduled everything from a home-made MS Access database, and kept paper work order files. The guys got their work orders for the entire week on Monday. This simple system worked like a charm. I've seen programs like Maximo and MaintainIt Pro in action, and the only way they work is if you have a support staff to run it (scheduler, planner, clerk, etc). A small site will not benefit from having a fancy program.
4. I asked the senior mechanic to give me his opinion on maintaining the equipment before I started a new procedure, and again after the procedure and work order were in use in the field. Remember that it's the guys who do the maintaining that make it work, not the software or procedure.
That's my 2 cents.