Both Ubuntu Phone (which is based on the same Linux distro as full Ubuntu) and Android run on a Linux kernel. However they differ above the kernel level, whereas Ubuntu runs a full GNU/Linux OS with most of the standard Linux libraries, and a GUI based on Qt, Android runs a custom Android and Dalvik platform instead.
It looks like one of the big benefits of them both being based on the same Linux kernel is driver support. This means that for any Android phone that has open-sourced drivers available (either officially from the manufacturer's source, or where a 3rd party ROM developer has written them), it should be a much easier to task to get Ubuntu Phone running on it. (notably pretty much every picture on the Ubuntu Phone site at the moment looks like it's of a Galaxy Nexus running Ubuntu Phone).
Ubuntu has already been adapted to run on chipsets using the ARM and
Intel x86 architectures relevant for mobile devices, with the core
system based around a typical Android Board Support Package (BSP). So
chipset vendors and hardware manufacturers do not need to invest in or
maintain new hardware support packages for Ubuntu on smartphones. In
short, if you already make handsets that run Android, the work needed
to adopt Ubuntu will be trivial.
(from http://www.ubuntu.com/devices/phone/operators-and-oems - my emphasis)
This means that, initially at least, it's phone manufacturers and Ubuntu enthusiasts who are going to see the biggest benefit - that it should be fairly easy to get Ubuntu Phone working on a handset that was designed for Android (and fairly easy to sell the same hardware with a choice of OS).
As the vast majority of Android apps are written using Java for the Dalvik VM, neither of which are guaranteed to be on an Ubuntu Phone (though enthusiasts may port them later) most of those apps won't work without a large amount of porting effort. Ubuntu themselves are unlikely to be in a hurry to port Java and Dalvik to Ubuntu Phone after the legal problems that Google have had with Oracle.
Also the Ubuntu Phone has it's own QML toolkit and Ubuntu SDK, neither of which are the same as (or compatible with) the Android SDK or NDK APIs, so again that's going to be a large amount of porting effort that will prevent Android apps from being run on Ubuntu straight away.
Web apps are first class citizens on Ubuntu, with APIs that provide
deep integration into the interface. HTML5 apps written for other
platforms can be adapted to Ubuntu with ease, and we’re targeting
standard cross-platform web app development frameworks like PhoneGap
to make Ubuntu ‘just work’ for apps that use them.
Despite all of those differences, history in the mobile space has shown us that if a mobile platform takes off in a big way, then no matter how big the time and effort needed to port apps between platforms, all the big apps and games will make their way to the new platform eventually and companies will come out with toolkits and software that makes it easy to write an app once that can then be compiled to run on any of the major platforms (that allow it).
It seems that most of Ubuntu's app-portability is concentrating on making it easy to convert web apps into Ubuntu Phone apps, and to make it easy to run exactly the same app on any Ubuntu device - desktop, laptop or phone:
With the arrival of the Ubuntu SDK, apps can be written to work on all
Ubuntu form-factors: it’s the same Ubuntu OS on the desktop and on the
phone, so a single native application can work on both. Which means
you re-use most of the app when you add support for a new form-factor.
Ubuntu Phone and Android are both based on a Linux kernel but are different above that - they can share drivers (this is good for manufacturers and hobbyists), but can't share apps. Ubuntu Phone shares apps with desktop Ubuntu, not with Android. They both have good web browsers and can view the same web pages.