I cannot find the Edit Regular expression button in for example konqueror on another KDE3 installation, why?

The regular expression widget is located in the package KDE-utils. If you do not have this package installed, then the edit regular expressions buttons will not appear in the programs.