Finding effective ways to encode data into DNA is not an easy task since the search space grows exponentially respect to the length of the oligonucleotides (single DNA strands) used in the task. In short, the problem of DNA Codeword Design (CD) is the optimization problem of finding large sets of short oligonucleotides which satisfy certain non-crosshybridizing constraints (combinatorial and/or thermodynamic). In this paper, a Multi-objective Evolutionary Algorithm (MoEA-CD) that exploits the structural properties of the DNA space to improve the speed and quality of candidate solutions to the CD problem is proposed. To this purpose, we consider the CD problem as a set covering problem, and we introduce two approximations mechanisms for computing the coverage and overlap of sets in such DNA space. The algorithm is tested in different DNA space dimensions, and our results indicate that MoEA-CD using such approximation mechanism maintains an excellent performance as the dimension of the search space is increased.