Turning a cold space into a warm space is absolutely doable, but the trick is doing it the right way to avoid creating longer term health or structural problems later.
The proper way to create a warm space is to create two different kinds of protections against the elements - a thermal break to hold in heat, and a moisture barrier to hold in water.
The thermal break is the obvious part - you want it to be warm, so you need to create a layer that doesn't conduct heat well and put it between your warm and cold spaces.
The moisture barrier is the less obvious and yet more important part. Wherever warm air touches a cold surface you get condensation. Condensation in an enclosed space - such as inside of a wall or insulated cavity - is a bad thing, because now you're getting organic materials such as wood and gypsum wet, which turns them from construction materials into mold food. Mold being bad (read - toxic) its important to create a complete barrier that keeps moist warm air from getting into cold, closed spaces. (Once the moisture gets into the wall it wont come out again anywhere near as fast as it got in, so it'll just keep building up).
The 2nd part here is you've got walls and a roof to deal with. Since you don't have a ceiling, and since it sounds like you don't really want to install one, you can treat the two the same. Thus I'll explain how to properly insulate your walls, and you can do the same for your roof over the garage. But bear in mind if you install a ceiling, then the roof has to be handled differently from the walls.
So - how do you insulate your walls safely?
First - yes you can use shredded denim insulation, or fiberglass, or cellulose, or spray foam. If cost is your primary concern, then you're going to trade off money for time.
The fastest but definitely not cheapest way to handle your problem is spray foam. With spray foam (closed cell foam being preferred over open cell foam) you spray (or have someone spray) a liquid compound into the wall cavities and the liquid foams up and then solidifies. What you get is a dense, seamless, tightly packed rigid material that has excellent insulation qualities and acts as a vapor barrier all on its own. In your case you could spray the walls and roof in one day and almost instantly have a workable warm space.
For any other kinds of insulation, its a bit more involved. The installation of the insulation is pretty straight forward - its the vapor barrier that's the issue. You can use fiberglass with paper backing, but personally I don't think that seals up as well, and I consider it a good idea to tape all the seams after they're stapled down, for extra measure... (taping seams will be covered more in a moment)
This is NOT how you install it:
Note how its all compressed and tucked in? That kills the insulation value (R-value). I've heard/seen it argued that you should tuck the backing in so that drywallers can glue the drywall to the framing - they use screws. I've never heard of drywallers doing this - and I don't think its worth surrendering the R-Value for drywall glue... Plus if they really do want to glue, well you install furring strips (as they did in the above pic) and glue to those...
IMO THIS is how you install paper backed fiberglass:
Flaps folded over the studs, and stapled down. (Then tape the seams for extra measure as well as taping any tears). I still also don't trust paper as a vapor barrier, though often times its paper/plastic laminate in which case it'll probably be fine.
Alternatively you can install an unbacked style (no paper, just insulation) - and then you add the vapor barrier by adding a layer of plastic, like so:
Here the plastic is hung up over top of the insulation, taped at its seams and so forth.
Here's the critical bit - YOU MUST NOT FAIL TO TAPE ANY SEAMS/GAPS IN THE VAPOR BARRIER.
A tiny pinhole in your vapor barrier can let in a whole cup of water in a season as warm moist air pushes into the cold space. So you have to create a completely solid barrier against moisture all the way around the edges, on all the seams, and in any tears you inadvertently create.
Because this vapor barrier is so important, you should drywall or protect it in some other fashion. (You want to create storage - consider sheets of plywood instead of drywall to create extra strong mounting surfaces for shelves ) If you leave the barrier exposed, it's gonna get damaged, and then its gonna lead to mold and rot.
If you spray foam, however, since its rigid and 4" thick, you can leave it exposed.