Hi and welcome,
I suggest you read a post on this topic at http://www.ashastd.org/phpbb/viewtopic.php?t=18
. Another discussion you might find helpful is at http://www.ashastd.org/phpbb/viewtopic.php?t=994
You can also review a discussion on HPV in relationships (including new partners) at http://www.ashastd.org/hpv/hpv_learn_relationships.cfm
With your new partner, it might help to use the dating process in order to get to know a them before telling them about HPV. As the relationship progresses toward sexual activity, suggesting a discussion about sexual histories might be a good way to introduce HPV as a topic.
It is important to keep in mind that this is not a confessional or apology - you have done nothing wrong. Caring for a partner enough to put their needs ahead of your own and trust them with a very intimate detail of your life is appreciated by most people.
Some talking points to consider including in a conversation with a new partner are that while HPV is very common, most never develop visible signs of the virus or health complications as a result. None of this is to minimize the impact of HPV by any means; rather, it's to offer a perspective that is often overlooked. This is also a chance to discuss safer sex practices, such as using latex condoms if they're appropriate to the relationship. Condoms don't eliminate the risks of STI transmission but when used consistently and correctly can diminish the risks, often a great deal. There is also evidence that HPV doesn't persist in most cases, due to the immune response.
After reviewing the links I posted, let us know if you have more questions. Thanks for being a part of our online community!
All the best,