Verify Magic Square

Python 2: 132 chars

n,l=input()
r=range
print r(1,n*n+1)==sorted(l)*len({sum(l[i::j][:n])for(i,j)in zip(r(n)+r(0,n*n,n)+[0,n-1],[n]*n+[1]*n+[n+1,n-1])})

An example run:

STDIN: 4,[16,3,2,13,5,10,11,8,9,6,7,12,4,15,14,1]
Output: True

The are two things to check:

1. The sums are the rows, columns, and diagonals are all equal
2. The elements are a permutation of [1,2,...,n*n].

The first is checked by taking sums of slices corresponding to these subsets. Each row, column, or diagonal is described by its starting value and its displacement. We take the list corresponding slice, truncate to n elements, and sum it. In Python's [start:end:step] notation, rows are [r*n::1], columns are [c::n] and the two diagonals are [0::n+1] and [n-1::n-1]. These are stored as a list of 2*n+2 pairs produced by zip.

We take the sets of sums and check that it has length 1. Also, we sort the input and check that it is the list [1,2,...,n*n]. Actually, we combine both into one check by multiplying sorted(l) by the length of the sum-sets, a check that always fails unless the sum-set has length 1.

APL, 35

∧/2=/(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕)

Explanation
x←⎕⍴⍨,⍨⎕ prompts for input, shape it into a matrix, and assign to x
⌽ Reverses the matrix left-to-right
x(...) Create a array of matrices: x and x reverse
1 1∘⍉¨ For each of those matrices, take the diagonal
+/↑ form a 2×n matrix of the numbers on those diagonals and sum the rows

⍉x Transpose x
x, then concatenate with x to form a n×2n matrix
+⌿ and sum the columns

(+⌿x,⍉x),+/↑1 1∘⍉¨x(⌽x←⎕⍴⍨,⍨⎕) concatenate to form an array of the sums
2=/ check if consecutive pairs equal
∧/ and AND together all those results

CJam, 47 39 35 33 31 bytes

l~/{_1fb_,Y${\(_@=\}%:++\z}2*;=

Takes input like

4 [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]

Outputs 1 if magic square, 0 otherwise.

How it works:

l~/                               "Evaluates the input and split the array into chunks"
                                  "of size N where N is the first integer";
   {                      }2*     "Run this code block 2 times";
    _1fb                          "Copy the 2D array and calculate sum of each row of copy";
        _,                        "Copy the array containing sum of each row and get"
                                  "its length. This is equal to N";
          Y${      }%             "Run this code block for each array of the original"
                                  "2D array that we copied from stack";
             \(_                  "Put the length number to top of stack, decrement and"
                                  "copy that";
                @=\               "Take the element at that index from each row and put"
                                  "N back behind at second position in stack";
                     :+           "Take sum of elements of the array. This is sum of"
                                  "one of the diagonals of the 2D array";
                       +          "Push diagonal sum to row sum array";
                        \z        "Bring original array to top and transpose columns";
                             ;    "At this point, the stack contain 3 arrays:"
                                  "  Array with sum of rows and main diagonal,"
                                  "  Array with sum of columns and secondary diagonal and"
                                  "  The original array. Pop the original array";
                              =   "Check if sum of rows + main diagonal array is equal to ";
                                  "sum of columns + secondary diagonal array";

This can be golfed further.

Try it online here