I've had great success with priceline for hawaii given the competition and price matching that goes on there. In fact I just secured a one week rental for $13/ day + tax [full size] vs the $25+ list rates. Even my gold club didn't come close... except on convertibles, so it pays to shop around directly as well!

Companies are varied but will generally be names you know: hertz, budget, national, avis, etc.

As far as what to bid, you have some time, so search the market and divide by 2 and make that your starting bid [you can try lower, sometimes it works]. There's a few tricks to the PL world but in short to bid multiple times in a single session you will either have to change your dates or car type. Since you want a specific type that means dates which can also be a problem... if you can't change either you're limited to one bid / day / person for a particular combination.

What's important to remember is that, unlike with a direct rental, you are paying upfront with no option to change / extend / cancel the agreement at all [I've negotiated out a few times but it took a lot of effort and a great reason]. To me the savings have to be at least 30% off of direct / coupon rates to justify the uncertainty and the lack of flexibility. And that's after tax to be clear.