How can I use object oriented principles in the following scenario?
Assuming all three companies require the same information, create a base class "CarRentalInformation."  This information will store/transmit all pertinent information.

Create serializer/deserializer classes for all types of can rentals you need.  You could probably use the factory pattern effectively here even if you need specialized information for each type you need.  

The logic could then be written as

public List&lt;CarRentalInformation&gt; GetCarRentalInformation(string XML)
{
   CarRentalXmlType xmlType = this.DetectCarRentalXmlFormat(XML);
   ICarRentalFactory deserializer = this.GetCarRentalFactory(xmlType);

   return deserializer.Deserialize(XML);
}

public string GetCarRentalXML(List&lt;CarRentalInformation&gt; rentalInfo, CarRentalXmlType xmlType)
{
   ICarRentalFactory serializer = this.GetCarRentalFactory(xmlType);
   return serializer.Serialize(rentalInfo);
}

private CarRentalXmlType DetectCarRentalXmlFormat(string XML)
{
   //do some magic detectivework, and return appropriate type
   return CarRentalXmlType.Budget;
}

private ICarRentalFactory GetCarRentalFactory(CarRentalXmlType xmlType)
{
   switch(xmlType)
   {
       case CarRentalXmlType.Budget:
          return new BudgetCarRentalFactory();
       case CarRentalXmlType.Dollar:
          return new DollarCarRentalFactory();
       default
          return null;
    }
}

public interface ICarRentalFactory
{
    public List&lt;CarRentalInformation&gt; Deserialize(string XML);
    public string Serialize(List&lt;CarRentalInformation&gt; rentalInfo);
}

public class BudgetCarRentalFacotry : ICarRentalFactory
{
   //contains code to serialize/deserialize XML into CarRentalInformation objects
}