Some things I would consider:
If you are a small company I doubt you will see any benefits to EDI. IMO the big boys shove it down your throat and that is why most small suplliers get into it. The time you save by not entering P.O. will not make up for all the time you burn setting up EDI translation maps (everybody does it different and the big boys have a motto, do it my way or we will find a supplier that will). You will also burn time dealing with communications issues, selecting a VAN, and/or dealing with AS2 configuration. AS2 cuts the middle man (VAN) out of the picture buy then you will need 24/7 monitoring of EDI communications. Lets just say some of the bigger players are not real friendly about AS2 problems either.
EDI is like an episode of Threes Company, every problem is a misunderstanding about some stupid missing value. The big boys complain if a zero or a blank is missing, some of them even complain when values they don't even use contain something. Your EDI person will spend lots of time on the phone or emailing customers about the most recent misunderstanding. But of course they are the 800 pound gorilla so they get what they want. Some also like to give you chargebacks if the smallest piece of data is missing or out of place, basically they treat EDI as a revenue source at your expense.
See if you can outsource it, dozens of companys offer this service. If your setup is neat, clean, and quick you might be able to do this. ASN's can be a major league pain in the butt depending on requirements.
If you can't outsource it try and find out what systems work best with your compute hardware situation. If you can't integrate it with your ERP then you will be doing everything twice in seperate databases. Once for your ERP system and once for your EDI system. Ask around, your ERP system supplier might even have some suggestions for you. If your ERP has a user group, milk them for some information. The most important decision you will make will be the first one, what software to get.
We have PRMS on an AS/400 and was able to integrate Inovis TrustedLink to it fairly well. The POs and invoices flow between them very well with few issues. When AS2 came a calling we went with Trailblazer and that is one quality product. It interfaced with Inovis so well that new EDI people can't even tell it is a seperate product.
You really need to do your homework on what packages work best with what you already have. Check their references and see what others are using that are in your same boat.