I have an Arduino Duemilanove clone. This->http://www.simplelabs.co.in/content/induinox-low-cost-arduino-usb-clone-board-atmega328
And i also have a new Atmega328p-pu. So i want to know if i remove the Atmega that is on the board and put in my new chip can i use it to run my arduino programs?
Not unless you first burn a bootloader onto the new blank 328p chip. To program the new chip with a bootloader while installed on your simplelabs board, you either need a hardware programmer compatible with one of the programmer choices that the arduino IDE uses. This programmer requirement can also be a working arduino board that has had the arduinoISP sketch loaded and wired to a blank chip on a breadboard. So it is possible for you to program your new chip if you install it onto say a solderless breadboard with all the proper wiring and a 16mhz crystal and loading the arduinoISP sketch to your simplelabs board.
Do i need to do burn the bootloader seperately or can i do it somehow on the board?
On the simplelabs board only if you have an external hardware programmer or another arduino board running the arduinoISP sketch wired to the ISP connector pins on your simplelabs board. Otherwise you can burn the bootloader separately as I stated above.
I understand its possible to burn a bootloader that doesn't use an external 16MHz crystal from this->http://arduino.cc/en/Tutorial/ArduinoToBreadboard
Yes, possible but it will make things more complex for you in the long run and will limit your sketch speed to 8Mhz rather then the more standard 16Mhz speed.
But i need an external crystal since i will use serial.
Serial can still work if the chip is using it's internal 8Mhz RC clock source, but higher baudrates can be a problem and it's better all around if you use an external 16Mhz crystal in my opinion.