Yes, PHP and a data-storage medium can do all the things you want to do.
I don't really think XML is a suitable info-storage medium. It seems to me that XML is the perfect medium for defining and exchanging data, but not for storing it. I think a relational database would be better ... and of course the one to choose for PHP would be MySQL (free, quite easy to learn and PHP offers strong native support for it). It is perfectly possible to construct search routines for MySQL and indeed there are lots of examples of that at this site. Updating is done on the database, not the PHP, as you correctly assumed.
As PHP supports both SQL/MySQL and XML, you may find it useful to use both media for your purposes. It remains to be seen.
Parsing: PHP code is a server-side web-programming language. It's client-side counterpart is Javascript. With Javascript, the language is supported and interpreted by the browser. With PHP, the language is supported and interpreted by the PHP engine residing on the web-hoster's server. PHP produces HTML (and Javascript and XML and a whole bunch of other things if you want) that is sent to the browser, but the browser never sees the PHP code. If you want to write and test PHP code at home, you need to install both the PHP engine and a web server (Apache, PWS, IIS, BadBlue) to intepret the code and write to your browser. Check out the forum 'Install' for extensive info on how to do this. It's not too hard.
I didn't know that there were many different parsers. As far as I'm aware there's only one, namely PHP, obtainable from http://www.php.net. If you mean editors, yes there are hundreds of those, some free some not. Check out the Echo Lounge for reviews of them. You can, however, write PHP in any old text editor, e.g. MS Notepad. The special editors are nice because they do colour coding and give you lots of groovy little extras, including debugging in some cases, but they're not strictly necessary.
For starters tutorials, check the net. There are thousands. Check the newbies forum at this site, also. I recommend getting a book, however (Sams, New Riders, Wrox, O'Reilly ...) for bedtime reading and as a reference to have beside your computer. Most PHP books delve into MySQL and XML as well (they should, if they're any good).
Best of luck, and if you do something interesting with PHP and XML, post it to these forums so that we can all learn something from it.
Norman