There are a few different effects these modes have.
Experience and money
These are both determined by the level of the Pokemon you beat. Playing in Challenge mode therefore means you get more experience and money from beating trainers, while playing in Easy mode means you get less--the opposite of what you might expect from the nominal difficulty.
The level term in the damage formula
As your level increases, your "bulkiness" against attacks manifests on a quadratic scale: the damage you take gets reduced by a larger defense stat, and that damage also makes less of a dent in your increased HP pool. To keep pace with this, the attacking side also needs some sort of quadratically-increasing factor, and the way the programmers implemented this is by multiplying their attack stat and their level together.
There's also a slight bit more complication and jaggedness to it, but suppose there's a trainer with level 37s, that gets adjusted up to "level 40" by the rules of Challenge mode. Even though the stats will still be calculated using level 37, so that part of the increase has no effect, the level term means that the level-37 attack stat, and the move power, will be multiplied by 18. In Normal mode, where everything is properly level 37 there, they would only be multiplied by 16, and in Easy mode (where the nominal level gets adjusted down to 34) they get multiplied by 15.
Early on in the game, there are some trainers for whom these changes don't even make a difference to the level term. For instance, the first rival fight at the beginning of the game after you've just picked your starter--you obviously need to use the Key System and link up with another game to have the additional modes unlocked that early, but level 5 (Normal) and level 6 (Challenge) both result in a multiplication by 4 for the level term, so the level-6 version of the starter doesn't actually hit any harder, and the only difference it makes in that case is giving you extra experience and money for beating it. In Easy mode, the level-4 starter only results in a multiplication by 3, so that one does cause it to hit softer. The latest trainers for whom this adjustment can possibly have no effect on the level term are the ones in and around Nimbasa City--adjusting level 25 up to 27, or 27 down to 25, is one of those cases that results in no change to the damage. (Later in the game, if you use Big Stadium or Small Court for grinding, you can get the same effect from adjustments like 60->62 or 62->60.) Once you get to Driftveil and reach the point where all trainers have their levels adjusted up or down by at least 3, that big of an adjustment is guaranteed to result in a change to the level term, and thus a slight increase or decrease to the damage.
Custom team specification
Game Freak deemed it too much work to do for every single trainer, but for Gym Leaders, Elite Four, and the Champion, they went even further than an automatic "take this team and adjust the nominal levels up or down" procedure; for these cases they could entirely rewrite the team for Challenge mode and use that custom one rather than the auto-generated one. This allowed them to give the gym leaders different moves, an extra Pokemon, different held items, and even changing their IVs to use all 30s instead of a lower value, like 12 or 18, that they might have in the other modes.
In these cases, the team's stats are still calculated using the unadjusted level from Normal mode. But the IV increase is properly taken into account (which often figures to add about the same number of stat points if it did calculate the level increase instead), the move and item changes are real, and the additional Pokemon you have to fight through is definitely real. Essentially, these changed teams are the main source of "Challenge" that gets added to the mode, in exchange for rewarding you with that extra experience and money.
The few trainers where the modified levels are actually real
There are three Funfest Missions in the game--"Train with Martial Artists," "A Path to an Ace," and "Sparring with __ Trainers"--that spawn dynamically-generated trainers onto the cities and routes. The gimmick is that each time you beat one, the next trainer's level will be increased by 1 when you fight them, and the Easy/Challenge adjustment applies on top of that. But because these trainers' levels are all generated on the fly, they decided to include the mode adjustment when calculating stats, which makes these the only cases where that's true. If you find the first ace trainer in the mission, with what would normally be a level 40 Swanna let's say, Challenge mode might adjust that up to level 44 depending on where you are on the map when you played the mission. In this case, the Challenge mode adjustment really does mean it gets the stats of a level 44 Swanna.
More to the point, if you have access to Easy mode, this is the one place where turning it on will actually reduce the amount of HP your opponents have (by calculating with level 36 instead of 40, for example), causing their HP bars to drain ever-so-slightly faster, and making it so you might just barely have room to squeeze in an extra trainer battle before the mission's time limit runs out. Worth a shot!
