Should I fertilize these trees

No.

Never fert stressed trees. And the thriving one doesn't need it either.

Dan

What makes you think the one with lots of new leaves is struggling?

Are your trees properly mulched? If not, the best thing you could ever do for your magnolias is to property mulch them as far out as you can justify. If you are not certain of proper mulching techniques, please ask for more info!

Brandon,

Yes, please tell me about mulching.

Thanks!

P.S. I think the one is struggling because the other one has beautiful, glossy green leaves as opposed to brown leaves that are falling off.

Probably evergreen magnolia which very often looks badly starved on local soils. Go to an independent garden center and ask for a suitable product.

Mulch all plantings except warm season vegetable crops. Use a entirely or partly more coarse mulch, like wood chips. Keep it away from stems.

I love cedar play chips originating at mills. Perfect!

 Bark mulch can be contaminated with salt or weed seeds
 Bark naturally contains waxes that prevent absorption and release of water in landscapes
 Sawdust is too fine a material to use as a landscape mulch and will prevent water and gas movement as
it compacts
 Softwood bark mulches are often not "gardener friendly" due to the presence of tiny, sharp fibers
 Arborist wood chips can be finely chipped if this is more aesthetically desirable

Here is a link that might be useful: The Myth of Pretty Mulch

I copied most of the following info off of my website, linked below. If it doesn't answer all of your questions, please let me know. I'm still trying to be sure I have all the bases covered.

Use an organic mulch like shredded hardwood, pine park, pine needles, etc. The mulch should be added at least as far out as the diameter of the planting hole. Wider mulched areas are beneficial. A tree's root system typically extends out two to three times as far as it's canopy. Proper mulch depth will vary with mulch type, but, if using pine bark or shredded wood mulch, 2" to 4" is generally sufficient. Mulching too deep can create surface drainage problems and deprive roots of oxygen. Remember to mulch wide, not deep. The area immediately adjacent to the trunk of the tree or shrub should be unmulched. Leave a couple of inches adjacent to the trunk bare to avoid fungal, disease, and pest problems. Excess moisture held against the bark on the lower portion of the trunk can encourage rot. Mulch placed against the bark can harbor disease and provide cover for gnawing rodents. In no case should "mulch volcanoes" be built around the trunk. Some gardeners make use of six to eight layers of newspaper or even cardboard under their mulch to reduce initial weed growth up through the mulch. Plastic, landscape fabric, and woven weed barriers should be avoided! These only cause major problems later on as seeds grow roots down though these materials and anchor themselves into the barriers. Removal can be problematic.

Here is a link that might be useful: Planting a Tree or Shrub