When you check in at CLE, make sure you have a printed itinerary for the whole out-bound trip. Assuming it was all booked under the same ticket #, CO in CLE will check your bags to your final destination (as long as you don't have an extremely long layover in LAX, usually 4-8 hrs is the cutoff) and you won't have to pay any excess baggage fees. If CO makes you collect your bags in LAX & re-check them, then you'd pay the fee to Air NZ upon checking them.

On the return, the same should happen by Air NZ when you're leaving, but you'll then be forced to go by their baggage policy, as they're the originating carrier.

Hope this helps!