The exponent can be arbitrarily close to $\frac{1}{2}$: If $n=r^2$ then $A+B=\lbrace 0,1,2,\cdots n-1 \rbrace$ where $A=\lbrace 0,1,2,\cdots r-1\rbrace$ and $B=\lbrace 0,r,2r,\cdots,(r-1)r\rbrace$. This means that $S=A \cup B$ is a set of size $2r=2\sqrt{n} $ with $S+S \supset \lbrace 0,1,2,\cdots n-1 \rbrace$. So by iteration (as described in the old answer) we can have exponent $\frac{1}{2}+\log_n(2)$.
Modifying this a bit gives a construction I probably have seen before: Let $A=\lbrace 0,1,4,5,16,17,20,21\cdots\rbrace$ be the (infinite) set of non-negative integers whose binary expansion is $0$ in all the odd positions and $B=2A$ the set of those with $0$ in all the even positions. Here both have exponent $\frac{1}{2}$ and $A+B=\mathbb{N}_0$. Then $S=A \cup B$ has about $2\sqrt{N}$ members less than $N$ and $S+S=\mathbb{N}_0.$
Old Answer Here is a nice ad hoc start: The set $S=\lbrace 0, 1, 3, 5, 6, 13, 15, 16, 18, 25, 26, 28, 30, 31 \rbrace$ has $S+S=\lbrace 0,1,2,\cdots,62 \rbrace$ (It is the start of a sequence in the OEIS with next term 63, but I'm not sure if that helps). Then $T=S+63S$ has 196 members the largest being $1984$ and $T+T=\lbrace 0,1,2,\cdots,3968 \rbrace$. Now $14=31^{0.63944}$ and $196=3968^{0.63699}$ and further iterating will continue to give examples sparser than $k^{2/3}$. The same trick can be done with any finite example. The densities decrease but only very very slightly.
LATER the set $S'=\lbrace 0, 1, 3, 5, 6, 13, 14,17, 18, 25, 26, 28, 30, 31 \rbrace$ also has $S'+S'=\lbrace 0,1,2,\cdots,62 \rbrace.$
Observe that the places where $S$ has a jump from $j$ to $2j+1$ are at $0,1,6,31$ (numbers of the form $\frac{5^j-1}{4}$) and that there is a central symmetry for $0,1$ and for $0,1,3,5,6$ and for $S$. This suggests a treasure hunt for an symmetric extension with largest member $1+5+25+125=156$.
UPDATE For any one of the four choices $(a,b)=(68,69),(68,72),(69,70),(70,71)$ the set $V=S \cup \lbrace 63, 64, a,b,156-b,156-a, 92, 93 \rbrace \cup (S+125)$ has $36$ members, the largest being $156$. and $V+V=\lbrace 0,1,2,\cdots,312\rbrace$ There is only one way to similarly extend $S'$ to a set of size $36$ with the same properties, it has lower half $S' \cup \lbrace 63, 65, 67, 69 \rbrace$. These are better than the examples above since $36=312^{0.62398}$. Also, these can be iterated as above.
Maybe an even lower density is possible for $W=V \cup \lbrace ?? \rbrace \cup(V+625)$ where the set in the middle is made of several pairs $q,781-q$. I'd guess 8 pairs leading to $88=1562^{0.60885}$ but that is pure speculation. Of course there might be better examples which are not symmetric (or even ones which are). There turns out to be no advantage at this stage to putting the exact middle of $78$ in $V$ (for any of the 5 choices). I don't think it would help get a better $W$ but I am not sure.
JHI's elegant lower bound of $8$ on $N$ is achieved by an explicit dissection.
I show my construction below; you might want to try to find
a solution yourself before proceeding $-$ it makes for a neat puzzle.
There may well be other ways to do it.
If somebody can make a "$3$-dimensional" graphic or picture of the
$8$-piece dissection, you're welcome to add it by editing my answer.
My diagrams are two-dimensional, labeling each piece with its height.
Fortunately the dissection is simple enough for this to be possible;
in particular, the eight pieces comprise four boxes and four L-shaped prisms.
This also made it possible to find the solution using just pencil and paper
on an otherwise uneventful international flight.
Begin by cutting the $6 \times 6 \times 6$ cube top to bottom
into three pieces, as shown in top view in the first square diagram.
Then cut each piece horizontally in two, dividing AB into $3+3$,$\phantom.$
C into $4+2$, and D into $5+1$. Each AB piece is then further subdivided
into a box B and an L-shaped prism A. The second diagram shows (say) the
bottom layer of four pieces, and the third diagram shows the top.
Note that the AB subdivisions are not quite the same.
(source)
Pieces with the same color will come together to form a smaller cube.
The larger C piece is a $4$-cube,
and the two A pieces form a $3$-cube as shown.
It remains to construct the $5$-cube from the remaining five pieces.
The last two diagrams show the bottom and top of the $5$-cube.
(source)
The two $5$'s are the larger B piece, rotated to span the entire
height of the cube, and the thick D piece.
The thin D piece completes the bottom, with width $1$.
The top is filled by the thinner C piece and the smaller B,
both rotated to height 4. QEF
I guess that a physical model won't make for a hard puzzle to reconstitute
into either one or three cubes (e.g. the AB, C, and D parts of the $6$-cube
are independent) but would still make a nice physical model of the identity
$3^3 + 4^3 + 5^3 = 6^3$.
This dissection is specific to the solution $(a,b,c;d)=(3,4,5;6)$ of the
Diophantine equation $a^3+b^3+c^3=d^3$; I don't know whether an $8$-piece
dissection is possible for any other solution. JHI's analysis shows that
one can never get below $8$, and in some cases even that's not possible:
if $a<b<c$ and $a+c<d$ then there's at least one corner of the $d$-cube,
say $(1,1,1)$, that contributes to the $a$-cube, but then any cell
$(x,y,z)$ with $\max(x,y,z) = a+1$ cannot connect to any corner.
This first happens for $(a,b,c;d) = (6,32,33;41)$.
What's the minimal dissection for the "taxicab" identity
$1^3 + 12^3 = 9^3 + 10^3$? JHI's corner-cutting argument shows
that at least nine pieces are needed.
Best Answer
This is the first problem in Chapter 9 of Martin Gardner, Penrose Tiles to Trapdoor Ciphers. In the addendum to the chapter, he writes that Herbert Taylor has proved it can't be done for $n\gt5$. Unfortunately, he gives no reference.
There may be something about the problem in Solomon W Golomb and Herbert Taylor, Cyclic projective planes, perfect circular rulers, and good spanning rulers, in Sequences and their applications (Bergen, 2001), 166–181, Discrete Math. Theor. Comput. Sci. (Lond.), Springer, London, 2002, MR1916130 (2003f:51016).
See also http://www.research.ibm.com/people/s/shearer/dts.html and the literature on difference matrices and difference triangles.
EDIT. Reading a little farther into the Gardner essay, I see he writes,
The only published proof known to me that the conjecture is true is given by G. J. Chang, M. C. Hu, K. W. Lih and T. C. Shieh in "Exact Difference Triangles," Bulletin of the Institute of Mathematics, Academia Sinica, Taipei, Taiwan (vol. 5, June 1977, pages 191- 197).
This paper can be found at http://w3.math.sinica.edu.tw/bulletin/bulletin_old/d51/5120.pdf and the review is MR0491218 (58 #10483).