Make a list of all the numbers that could satisfy each clue i.e. a list of all the perfect squares, another of all the prime numbers etc. It might be a good idea to list underneath the possible squares that these numbers go in.
Write the numbers from 1 to 25 and cross them out as you fit them in the magic square.
You should be able to work out the median straight away.
Look for squares that are listed in more that one clue to get you started.
Keep crossing off numbers and squares from your lists as soon as you've placed them in the magic square - you'll soon notice that some answers will just fall out!