the hanging rails as recommended above are great, can be very strong with plenty of screws and you can add extra cabs, or move them around, with great ease. You will need to make a rail-shaped notch in the sides of the cabinets so they can press neatly against the wall. There is a way of hiding this in an elegant kitchen, and you can paint the rail to match the wall, but it doesn't matter in a garage.
btw a simple DIY way of setting plugs into crumbly blocks or awkward bricks, clean out all the dust with a vac, and squirt in some builders adhesive, of the no-more-nails type, starting with the nozzle right at the back of the hole so there is no air bubble. Press in your plasplugs so that they squeeze into the adhesive; clean off excess; leave to set overnight before driving in your screws. The adhesive will prevent the plugs from rotating and will transmit the expansive force to the block with no crumbling.
When using the long rails, screw in one end, then adjust the rail for level, drill and screw the one at the other end, then use the holes in the rail as the guide for all the other holes. having marked them, you can undo one of the end screws and let the rail swivel out of your way. As a minimum, you need one screw at each end, and one within a few of inches of each place where a hanger will go. Cabs are usually in 500mm or 600mm widths.
you can also hang tools or coats direct to the rail using "S" shaped hooks