You have to use all the information available to you, including the in-game appraisal system. Learn what the phrases your team leader uses mean, and use that information to help you narrow down the possibilities.
Example
Take this Weedle as an example
If you enter in the information from this screen into the IV Calculator at Poké Assistant, you'll end up with 14 possibilities.
If you use the in-game appraisal, the team leader indicates that HP is the best stat, and that it's either 13 or 14. If you enter in that information, you'll only be left with 6 possibilities.
However, the team leader also said that the Pokémon was "decent" (team Valor), so you know the Pokémon must be between 51.1% - 64.4% perfect. This means that you can exclude the last four items that Poké Assistant listed, leaving you with only two possibilities.
From there you can further narrow the possibilities down by powering up the Pokémon, and entering the new values into the calculator. Using a second calculator can also help you narrow it down.
At any rate, the evaluation is based on the Pokémon level, not the trainer level. You can estimate the level of a Pokémon, by looking at the stardust required to power it up. In my example above, the Weedle must be either level 13 or 14, based on the stardust required to power it up.
To answer the question directly, the IVs don't change based on level. What an IV calculator is showing you, is all the possible IV combinations that would produce a Pokémon with the stats you entered.
In the above example, a level 13 Weedle with 5/0/14 IVs, and a level 13 Weedle with 0/10/14 IVs, both result in a level 13 Weedle with 131 CP and 45 HP. The only difference would be the IV distribution, and the percent perfection.
Best Answer
In summary it uses trial and error. There is a sheet of game data which has base stats and then a bunch of functions that just try different values of IV that would match the numbers you have given it. Since a given CP/HP combination can have multiple possible sets of stats it suggests levelling it up and trying again and this way it can eliminate some of the incorrect possibilities.
In more detail this is the algorithm that is uses...
It works out level of Pokémon (and levels can be halves as well as whole numbers) by the stardust cost of the next upgrade (table is in the game data sheet). The "powered up?" column determines whether these half levels are actually allowed. If "powered up" is TRUE then it will allow half levels, otherwise the level must be a whole number. I assume this is because pokemon when caught will always have an integer level.
It then loops through all possible levels getting all the combinations of stats that work for that.
2.1. First for a given level it works out possible stamina values. Each level has a CP multiplier (in the game data sheet). IV stamina can be anything from 0 to 15. It adds this value to the base stamina of the pokemon and multiplies it by the CP value. It then takes the floor of this value (so taking just the whole number part so 59.9 would be 59). If this matches the HP you were given then the stamina is a valid possibility.
2.2 Attack and Defence are also between 0 and 15 and it tries all 256 combinations of those with the possible staminas. It works out the CP for each possible combination and any that match the CP you have given it are added as possibilities.
2.2.1 CP is worked out by taking the attack ((base+IV)*CPMultiplier), the square root of the defence ((base+IV)*CPMultiplier), and the square root of the stamina ((base+IV)*CPMultiplier), multiplying them together and dividing by 10.
This gives you your list of possibilities.
Once you try again after a level up because of the way the rounding works some of the previous calculated possibilities will likely differ by 1 (or maybe more) and therefore can be discounted. Do this enough times and it will work out a unique set of values for the stats.
The Dratini example should show you how this works. Follow through the maths on each of them to see how it works.
If you have any questions on specific bits of this operation then let me know and I'll see if I can clarify anything.
Source: This information is all derived from reading the scripts in the script of the sheet. You can see the code once you have copied the sheet for yourself by clicking on "Tools...Script Editor..."