Here are some observations that reduce the search space somewhat.
There are only 22 possibilities for the last 2 digits of a perfect square:
00 01 04 09 16
21 24 25 29 36
41 44 49 56 61
64 69 76 81 84
89 96
These can be obtained by scanning a table of the squares of the numbers 0-99. Each of the 2-digit endings has 4 "square roots" in 0-99 except for 00 and 25, which have 10 each. We can reject 00, 01, 04, 09 and 44 as not meeting the constraints of the problem. And if we look a little deeper into the 10 "square roots" of 25, we find that only 25^2 and 75^2 will work for us because the squares of all the other "square roots" end in 025 or 225.
Let's say we are working on the first part of the problem,finding the smallest square consisting of the digits 1-9. We may tentatively assume that the first digit will be 1. With this assumption we can rule out the squares ending in 1, leaving us with
16 24 25 29 36
49 56 64 69 76
84 89 96
-- 13 possibilities in all, with 50 "square roots" in 0-99 (taking into account the observation about "square roots" of 25 above). So we have reduced the search space by 1/2.
[edit]I didn't express that part about the square roots of 25 clearly. What I mean is that if you have a number of the form
$\displaystyle 100x + 5a$ where a is odd and in the range 0 through 19
then its square is
$\displaystyle 10000 x^2 + 1000 ax + 25 a^2$
so the last two digits are determined by
$\displaystyle 25 a^2$
and we only have to check a few possibilities to find out that only a = 5 and a = 15 will work, so 5a = 25 or 75.
[/edit]
The fact that Dudeney asks for the largest and smallest suggest that his search space was not quite as small as he might have liked. Searching from the top downwards until one finds a solution and then from the bottom upwards requires far less work than finding the 10th largest (which project Euler might have asked for if mechanised search were not so easy).
CB
I just found that the 30 solutions to the problem are sequence A071519 in the Sloan On-Line Encyclopedia of Integer Sequences:
A071519 - OEIS