What does the dual of a tensor mean (e.g. dual stress tensor in relativistic ED)? I know what the dual of a vector means (as a map to its field), and I am also 
aware of of the definition a dual of a tensor as,
$$F^{*ij} = \frac{1}{2} \epsilon^{ijkl} F_{kl}\tag{1}$$
I just don't understand how to connect this to the definition of the dual 
of a vector. Or are they entirely different concepts? If they are different 
then why use the word dual for it?
I know this is kind of mathematical or may be a stupid question, but I have a
problem with understanding the need for dual of Dual Field strength Tensor 
in relativistic ED. I mean you could say that I am going to define another 
tensor using eq. (1) call it whatever we like.
 A: The dual of a tensor you refer to is the Hodge dual, and has nothing to do with the dual of a vector. The word "dual" is used in too many different contexts, and in this case it is even used the same $*$ symbol. One usually specifies "Hodge dual", or "Hodge star operator", to avoid confusion. Both these "duals" are isomorphisms between vector spaces endowed with inner product.
The dual of a vector space $V$ is the vector space $V^*$ consisting in the linear functions (functionals) $f:V\to \mathbb R$ (or $\mathbb C$ if $V$ is a complex vector space). The dual of a vector $v\in V$ makes sense only if $V$ is endowed with an inner product $g$, and it is defined as $v^\flat\in V^*$, $v^\flat(u)=g(v,u)$. This dual is an isomorphism between the inner product vector space $(V,g_{ab})$ and its dual $(V^*,g^{ab})$.
The Hodge dual is defined on totally antisymmetric tensors from $\otimes^k V$, that is, on $\wedge V^k$. It is defined on $\wedge V\to \wedge V$, where $\wedge V=\oplus_{k=0}^n\wedge^k V$. It also requires the existence of an inner product $g$ on $V$. The inner product extends canonically to the entire $\wedge V$. 
The Hodge dual is defined as follows. We construct a basis on $V$, which is orthonormal with respect to the inner product $g$, say $e_1,\ldots,e_n$. Then, for each $k$, there is a basis of $\wedge^k V$ of the form $e_{i_1}\wedge\ldots \wedge e_{ik}$. This basis is considered to be orthonormal too, and by this, $g$ defines an inner product on $\wedge^kV$.
The Hodge dual is defined first between $\wedge^kV\to\wedge^{n-k}V$, Both spaces have the same dimension, which is $C^k_n$. The canonical isomorphism between them is defined first on the elements of the basis:
$$*(e_{i_1}\wedge\ldots\wedge e_{i_k})=\epsilon e_{j_i}\wedge\ldots\wedge e_{j_{n-k}}.$$
Here, the indices $i_1,\ldots,i_k,j_1\ldots j_{n-k}$ are a permutation of the numbers between $1$ and $n$. $\epsilon$ is $+1$ if the permutation $i_1,\ldots,i_k,j_1\ldots j_{n-k}$ is even, and $-1$ otherwise. This defines uniquely the isomporphism. It extends uniquely to $\wedge V=\oplus_{k=0}^n\wedge^k V$, since this is a direct sum of vector spaces.
Please note that the vectors also admit Hodge duals, but their duals are elements of $\wedge^{n-1}V$.
Since we can consider that $\mathbb R=\wedge^0 V$, the Hodge dual of the scalar $1$ is the volume element $*1:=e_1\wedge\ldots\wedge e_n\in\wedge^n V$. In a basis, it is denoted by $\epsilon_{12\ldots n}$.
Similarly, the Hodge dual can be defined on the space of exterior forms $\wedge V^*$.
In the case of Lorentzian spacetimes of dimension $4$, the Hodge duality establishes isomorphisms between $\mathbb R$ and $\wedge^4 V$, between $V$ and $\wedge^3 V$, and between $\wedge V^2$ and itself.
An alternative way to construct the Hodge duality is for the Clifford algebra associated to $V$. In this case, there is an isomorphism (as vector spaces with inner product) between $\wedge V$ and $Cl(V)$. The Hodge dual translated to the Clifford algebra language as Clifford multiplication with the $n$-vector which corresponds to the volume element, $\gamma_1\cdot\gamma_2\cdot\ldots\cdot\gamma_n$.
Back to the confusion of terminology. For a vector $v\in V$, the dual is a covector $v^\flat\in V^*$. The Hodge dual can be obtained by constructing an orthonormal basis starting from $v$, then taking the wedge product between the other elements, and dividing by the length of $v$. The result is from $\wedge^{n-1}V$, not from $V^*$. All these three spaces are isomorphic, in a canonical way, and also with $\wedge^{n-1}V^*$, by composing the two kinds of dualities. But the two dualities refer to totally distinct isomorphisms.
In connection with Electrodynamics (in Lorentzian spacetime), the Hodge dual of the electromagnetic tensor appears in Maxwell's equations:
$$d F=0$$
and
$$d *F=*J$$
where $J$ is the current $1$-form. These two equations contain the four Maxwell equations. Here, $*F$ is the Hodge dual of the electromagnetic tensor $F$, and $*J$ of the current $1$-form $J$ (which in turn is the "dual" in the other sense of the current vector).

Added
To be more close to the question. The equation 
$$*F_{ij} = \frac{1}{2} \epsilon_{ij}{}^{kl} F_{kl}$$
represents the Hodge duality between $\wedge^2V$ and itself. But 
$$*F^{ij} = \frac{1}{2} \epsilon^{ijkl} F_{kl}\tag{1}$$
is a duality between $\wedge^2V$ and $\wedge^2V^*$. There is also the duality in the first sense, between $\wedge^2V$ and $\wedge^2V^*$ (extending that between $V$ and $V^*$). So, there are two distinct isomorphisms between the vector spaces with inner product $\wedge^2V$ and $\wedge^2V^*$.
A: Cristi Stoica's answer that the two notions of duality are completely different from each other is repeated by several standard textbooks; see exercise 3.14 on page 88 of "Gravitation" by MTW and section 4.9 on page 125 of "Geometric methods of mathematical physics" by Bernard Schutz. In spite of this, I'll show that the  two notions of duality are the same. 
Let $e_{a}$ for $a=1,\ldots,m$ be a set of basis vectors spanning the
vector space $V_{m}$. The vector $e_{a}$ has components $e^{i}_{\ a}$
where $i=1,\ldots,m$. The quantity $e^{i}_{\ a}$ can be studied as 
an $m\times m$ matrix. Letters $i,j,k$ will be used for components 
of a vector and $a,b,c$ will be used to label the basis vectors themselves. 
The dual space $\tilde{V}_{m}$ is spanned by the dual basis vectors
$e^{a}$; the basis vectors and the dual basis have scalar products
$\langle e^{a}|e_{b}\rangle=\delta^{a}_{b}$. The scalar product is a 
contraction,
$$
\langle e^{a}|e_{b}\rangle=
[e^{a}]_{i}[e_{b}]^{i}=[e^{a}]_{i}e^{i}_{\ b}=\delta^{a}_{b} 
$$
so that the dual basis vector $e^{a}$ has components $[e^{-1}]^{a}_{\ i}$;
as a matrix, the set of dual basis vectors is the inverse of the
matrix for the set of basis vectors. Cramer's rule says,
$$
[e^{-1}]^{a}_{\ i}=\frac{1}{\det{e}}
\epsilon_{k_{1}\ldots i\ldots k_{m}}e^{k_{1}}_{\ 1}\ldots \check{e^{k_{a}}_{\ a}}
\ldots e^{k_{m}}_{\ m}
$$
where component $i$ on the RHS is in the $a$th place in the
Levi-Civita tensor and the check over the basis vector $e_{a}$ means
it is omitted. Cramer's rule shows that one can make the dual vectors
$e^{a}$ that span $\tilde{V}_{m}$ by a contraction of the $m-1$
basis vectors $e_{1}\ldots \check{e_{a}}\ldots e_{m}$ with the 
Levi-Civita tensor. The notion of duality that makes new tensors
by contracting with the Levi-Civita tensor is said to have
nothing to do with the duality between a set of basis vectors
and the dual basis, but Cramer's rule shows that one can get the set 
of dual basis vectors by contracting sets of basis vectors with
the Levi-Civita tensor: the two notions of duality are, in fact, the same.
A: This is in fact a comment to the answer of Stephen Blake. It was suggested to me to reply, and I think I should do, but the reply is too long for a comment.
It is correct what is said in Stephen Blake's answer about Cramer's rule. It is not correct that the two dualities are the same. I think there is a confusion there, which may make the reader more confuse. There are three spaces involved, and three isomosrphisms, from which one of them is obtained by composing the other two. But there are at least two isomorphisms to start with, not just one, as Stephen Blake claims. Please refer in what it follows both to my answer, and to Stephen Blake's answer.
The Hodge dual between $\wedge^k V$ and $\wedge^{n-k}V$ can be expressed by using the Levi-Civita symbol in the form
$$\epsilon_{i_1\ldots i_k}{}^{i_{k+1}\ldots i_{n}}$$
by $$(*A)^{i_{k+1}\ldots i_{n}}=\frac{1}{k!}\epsilon_{i_1\ldots i_k}{}^{i_{k+1}\ldots i_{n}} A^{i_1\ldots i_k}$$
This form of the Levi-Civita symbol is obtained by raising some of the indices of the following form of the Levi-Civita symbol
$$\epsilon_{i_1\ldots i_ki_{k+1}\ldots i_{n}}.$$
They are usually considered to be the same because of the musical isomorphisms, which are in fact the duality isomorphisms between $V$ and $V^*$.
$$\epsilon_{i_1\ldots i_k}{}^{i_{k+1}\ldots i_{n}}=g^{i_{k+1}j_{k+1}}\ldots g^{i_{n}j_{n}}\epsilon_{i_1\ldots i_k j_{k+1}\ldots j_{n}}.$$
The Levi-Civita symbol $\epsilon_{i_1\ldots i_ki_{k+1}\ldots i_{n}}$ establishes an isomorphism between $\wedge^k V$ and $\wedge^{n-k}V^*=(\wedge^{n-k}V)^*$. I exemplified this in my answer, for $n=4$ and $k=2$.
It is a matter of convention whether to define the Hodge dual as the isomorphism between $\wedge^k V$ and $\wedge^{n-k}V$ (this was my choice), or that between $\wedge^k V$ and $\wedge^{n-k}V^*$. After the definition is given in one or the other way, to pass from one of the two isomorphisms to the other, we use the musical isomorphism (the duality isomorphism between between $V$ and $V^*$).
It is true that we can obtain by Cramer's rule the dual of a basis in $V$, by using the Levi-Civita symbol, but this is not quite the isomorphism between $V$ and $V^*$. It is instead the isomorphism between $\wedge^{n-1}V$ and $V^*$. And if we want to identify $\wedge^{n-1}V$ with $V$, we use implicitly the Hodge dual between them. So, the claim that the two dualities are the same is based on using both the definition of the Hodge dual as the isomorphism between $\wedge^k V$ and $\wedge^{n-k}V$, and that between $\wedge^k V$ and $\wedge^{n-k}V^*$. The duality between $V$ and $V^*$ was obtained by composing the two versions of Hodge dual, which contain implicitly the musical isomorphism. So two of the three isomorphisms are fundamental.
On the other hand, as I explained in my answer, the Hodge dual is constructed using the inner product, which can be viewed as the duality between $V$ and $V^*$. In this sense, the duality between $V$ and $V^*$ is more fundamental.
