clang and clang++ not found after installing the clang-3.5 package

It's there, but it's still called clang-3.5.

You can either execute it as clang-3.5 (or clang++-3.5) or setup a symlink to it like I did (installing regular clang didn't work):

sudo ln -s /usr/bin/clang-3.5 /usr/bin/clang
sudo ln -s /usr/bin/clang++-3.5 /usr/bin/clang++

Ugly work-around, perhaps; but at least it works for now :)

The proper way to use clang as your default cc and c++ is to use update-alternatives:

It is possible for several programs fulfilling the same or similar functions to be installed on a single system at the same time. For example, many systems have several text editors installed at once. This gives choice to the users of a system, allowing each to use a different editor, if desired, but makes it difficult for a program to make a good choice of editor to invoke if the user has not specified a particular preference.

so first you need to add clang-3.5 or clang++-3.5 as alternatives to e.g. gcc and g++:

sudo update-alternatives --install /usr/bin/cc cc /usr/bin/clang-3.5 100
sudo update-alternatives --install /usr/bin/c++ c++ /usr/bin/clang++-3.5 100

If at any time you need to switch back to gcc or g++ you can use the --config option:

sudo update-alternatives --config c++

On Ubuntu 15.04 you can also install the clang package along the clang-x.x package. You can then type clang++ and the according executable should be found.

sudo apt-get install clang

Adding to Yan Foto's answer (and just in case your aim is to get a usable clang but not necessarily use it as cc), you can actually add the entire set of programs in one go using

sudo update-alternatives --install /usr/bin/clang clang /usr/bin/clang-3.8 380 \
--slave /usr/bin/clang++ clang++ /usr/bin/clang++-3.8 \
--slave /usr/bin/clang-check clang-check /usr/bin/clang-check-3.8 \
--slave /usr/bin/clang-query clang-query /usr/bin/clang-query-3.8 \
--slave /usr/bin/clang-rename clang-rename /usr/bin/clang-rename-3.8

(Note that the set of binaries that come with each clang version might differ, e.g. 3.6 does have clang-tblgen, 3.8 doesn't.)

If you repeat this for every version of clang you install, you'll be able to switch between them using just a single update-alternatives command.

(Meanwhile, apparently, there is still an ongoing debate about whether to include these links with Ubuntu packages or not: https://bugs.launchpad.net/ubuntu/+source/llvm-3.1/+bug/991493)