Must a deleted constructor be private?

They are different only wrt the produced diagnostics. If you make it private, an additional and superfluous access violation is reported:

class A
{
public:
    A() = default;
private:
    A(const A&) = delete;
};

int main()
{
    A a;
    A a2=a;
}

results in the following additional output from GCC 4.8:

main.cpp: In function 'int main()':
main.cpp:6:5: error: 'A::A(const A&)' is private
     A(const A&) = delete;
     ^
main.cpp:12:10: error: within this context
     A a2=a;
          ^

hence my recommendation to always make deleted methods public.