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.

I want to extend Daniel Frey's answer. Instead of making deleted methods always public, I would rather give these methods the access modifier you would (hypothetically) give these methods if they would not be deleted. (I do not like always in case a programmer has an option. If it would indeed be carved in stone to make deleted methods public, it should be enforced by the language itself.)

Some rules of thumb/guidelines:

• Copy and move assignment operators will be public in concrete and abstract classes for most cases.
• Copy and move constructors will be public in concrete classes for most cases.
• Copy and move constructors will be protected in abstract classes for most cases.
• Copy and move constructors will be private in concrete final classes that can only be instantiated by friends for most cases.

In all cases, you make an announcement to the appropriate users of a class instead of all users of a class.