My supervisor asked me to make an Abbreviations and Symbols part to my thesis
This is a reasonable request: when there are many symbols, a list can be definitely helpful to the reader.
Now, obviously I won't put every variable (and abbreviation) into this list.
You won't put every variable, but you surely want to put any abbreviation.
What should the criteria be for putting an entry to the list?
I suggest you to put: special quantities which are defined in your work; special operators and functions; mathematical spaces; and all the abbreviations, even those you think are well known in your field.
I also have tried to explain the variables where I'm using them, is this now redundant when done in conjunction with the list?
No, it's not redundant because a list of symbols does not typically give the complete definition, but just a short one. Actually, it would be also useful to list the page number where a certain symbol has been defined for the first time.
Additionally, should the symbols and abbreviations appear in the list
in alphabetical or appearance order?
If you can define an alphabetical order, go for it. Unfortunately, this is not always possible (in a universally recognized way) with symbols. In any case, I'd separate symbols and abbreviations.