If I understand correctly, you're asking how to prove that symmetry of a tensor is coordinate independent, but you seem to be having trouble with the definition of a tensor. Well, you're not the first. Let me give you a definition that might help.
First, suppose you have some space (it can be 3-space or spacetime or whatever) and you have a set of coordinates $\{x^i\}$ defined on it. And let's say you have a particle moving in your space, with a trajectory given by $x^i = x^i(t)$. Here $t$ is just a parameter. You can find the components of the velocity in your system of coordinates: $u_x^i(t) = dx^i/dt$. (I am using subscripts to label coordinate systems.) Now here's the thing:
Suppose you calculate the velocity in a different system of coordinates $\{y^i\}$; it would be $u_y^i(t) = dy^i/dt$. But if you know the coordinates $y^i$ as a function of the coordinates $x^j$, you can find out how the two velocities are related:
$$u_y^i(t) = \frac{dy^i(x)}{dt} = \frac{\partial y^i}{\partial x^j} \frac{d x^j}{dt} = \frac{\partial y^i}{\partial x^j} u^j_x(t)$$
I have used the chain rule and the fact that the $y^i$ are functions of the $x^j$. $\partial y^i / \partial x^j$ will have different properties depending on the coordinates. In Euclidean 3-space we tipically use Cartesian coordinates and so $\partial y^i / \partial x^j$ would be a rotation matrix; in Special Relativity it would be a Lorentz transformation, and so on. In General Relativity we use all kinds of coordinates, and the transformations will not in general be linear.
So now we know how the velocity of a particle (or, as the mathematicians would call it, the tangent vector to a curve) transforms when you change coordinates. It is often helpful to regard such a vector as an object $\vec{u}$ that is independent of coordinates. Indeed, this whole business of transformation laws and Einstein convention is a way to make sure that things don't depend on coordinates. The components of a vector (or a tensor) will depend on the coordinates, but if everything transforms the same way, equations made out of tensors will have the same form in different coordinate systems.
Now we can define vectors in general, by asking that they have the same transformation law as velocities:
A vector $\vec{X}$ is a function that assigns a set of numbers (called its components) $X_x^i\ (i = 1\dots n)$ to each coordinate system $\{x^i\}$, such that if $\{x^i\}$ and $\{y^i\}$ are two coordinate systems, the components of $X$ are related by
$$X_y^i = \frac{\partial y^i}{\partial x^j} X_x^j$$
Side note: What I have defined is technically a vector field, not a plain vector. This is not an important distinction here. Also, I am restricting myself to coordinate bases for simplicity.
This is essentially the same as the "set of numbers that transforms like this" definition, but I find it to be a bit clearer and more explicit as to what things are.
A tensor can be defined as something that transforms as products of vectors: If we take two vectors $\vec{u}$ and $\vec{v}$ and define the (coordinate-dependent) quantity $T_x^{ij} = u^i_x v^j_x$, then in two different coordinate systems we find (defining $\Lambda^i_{\ j} = \frac{\partial y^i}{\partial x^j}$):
$$T^{ij}_y = \Lambda^i_{\ k} \Lambda^j_{\ l} T^{kl}_x$$
Following the definition of a vector, we can define a $(2,0)$ tensor $T$ (not necessarily a product of vectors as above) as a function that assigns a set of numbers $T^{ij}_x$ to each coordinate system, such that the components in two different systems follow the above transformation law.
Now let's get to your question. You ask how to prove that a symmetric tensor is a tensor, but this is a tautological question, because a symmetric tensor obviously is a tensor! I suspect that the actual question is as follows. You defined a symmetric tensor as one that has the property $T^{ij} = T^{ji}$. This is a valid definition, but it is a priori coordinate dependent. We would like to prove that if the above identity is true in one coordinate system, it is true in all of them.
So let's suppose in some coordinates $\{x^i\}$ it happens that $T_x^{ij} = T_x^{ji}$ for all $i,j$. Let $\{y^i\}$ be an arbitrary coordinate system. Then
$$T_y^{ij} = \Lambda^i_{\ k} \Lambda^j_{\ l} T^{kl}_x = \Lambda^i_{\ k} \Lambda^j_{\ l} T^{lk}_x = \Lambda^j_{\ l} \Lambda^i_{\ k} T^{lk}_x = T_y^{ji}$$
To get the second equality I used that $T_x^{kl} = T_x^{lk}$, to get the third equality I moved the $\Lambda$s around, and in the first and last equalities I used the transformation law for a tensor. So we have found out that if a tensor is symmetric in some coordinate system, it is symmetric in any coordinate system. Therefore, it makes sense to say that symmetry is a property of the tensor instead of its representation in a particular coordinate system.
One final remark: As you said, a tensor with two indices can be represented as a matrix. The derivatives of the transformation $\partial y^i / \partial x^j$ can also be represented as a matrix. These matrices have different meanings! A tensor is a coordinate independent object, and its matrix will change if you change coordinates. A transformation is defined only between a specific pair of coordinate systems. If you have a matrix $\Lambda^i_{\ j}$ relating coordinates $x$ and $y$ as above, it makes no sense to ask what $\Lambda$ looks like in coordiantes $z$. So even though a symmetric tensor has a symmetric matrix ($A^T = A$) and a rotation matrix is orthogonal ($A^{-1} = A^T$), these properties are unrelated to each other.