I know (or at least was taught) that ALL C++ programs must #include<iostream>.
Not true, you can have a C++ program without, It'll just be difficult to get any console output, and to give input. 99% of GUI applications don't use iostream.
As for your problem, check that you have devel headers installed (my iostream is at /usr/lib64/gcc/x86_64-pc-linux-gnu/4.4.4/include/g++-v4/iostream). If you have everything installed, then you can specify a custom path for kdevelop to look for any includes (the only way I know how to do this is to hover over the undefined header, a little question popus appears where you can either ignore or select a custom path. Usually though this means that you don't have a -devel environment (read headers) installed.
If using ubuntu, a package called build-essentials should get you up and running.