Stan, the labor and new foam and attaching hard velcro is in the $1500-$1600 range .. The material itself can skew the price a lot.. My 34 needed 10 yards of upholstery material, so I am going to guess your 36 would need a couple more.. I re-did only the main cabin cushions and not the vee berth or aft cabin cushions.
The material can be had for anywhere from about $15 a yard to around $100 a yard, depending on what you want. The Field's Fabric folks and the SailRite folks sell sample kits so you can actually see and touch the material. I tried to find stuff in Baton Rouge fabric stores but no one had the kind of stuff I was looking for.