How to install celeryd package with python3-celery

Have you tried just installing all these packages at the same time?

sudo apt-get install python-celery python3-celery celeryd

For a more specific answer please tell which Ubuntu release you are using!

Ah ok. So, there appears to be an missing dependency on 'python-celery-common', and an undocumented behaviour that it looks to see if python3-celery is installed and if so runs that, and if it isn't runs python-celery. So the dependencies for this package seem rather broken unfortunately.

I suggest you report a bug to get the dependencies resolved

When digging into the celery packages, there really seems to be some strange dependencies.
Taking celery 3.1.20-1 in xenial as an example:

celeryd depends on python-celery and creates a link for the changelog into python-celery
python-celery-common depends on python3-celery OR python-celery, but creates a link for the changelog into python3-celery (which might point to nowhere if only python-celery is installed but not python3-celery)
python-celery has no dependency on other celery packages
python3-celery also has no dependency on other celery packages

I conclude that for running celery with python3-celery you need to install both packages celery and python3-celery, and this will also install python-celery

If you can make a proposal how to improve the dependencies between the packages, you are invited to create a bug report.

You are correct with the "undocumented behavior": The /usr/bin/celery script tries to find celery on python3, if that is not found, then it looks for celery on python2.7, if that is not found, it looks for celery on python2.6, and if that also does not exists, it aborts with the message that python-django (!) is not found.

OK I've created a bug report (#1673041) and linked to it from this question.